Minimum bulma
- Algoritmalar kursu
- Başlangıç
- Ders 26/80
- 4 dk
Bir dilimde en küçük elemanın indeksini bulmayı öğrenirsin.
Yer değiştirme
Minimum bulunduktan sonra, onu sıralanmamış bölümün ilk elemanıyla yer değiştirirsin. Bu, o elemanı doğru yerine koymuş olur.
Yer değiştirme O(1) zaman alır: yalnızca iki eleman değiştirilir. Toplamda n-1 yer değiştirme yapılır.
Sıralanmış bölüm büyümesi
Her yer değiştirmeden sonra sıralanmış bölüm bir eleman büyür. Selection sort, baştan sona doğru sıralanmış bölümü genişletir.
i. adımda, ilk i eleman sıralıdır ve geri kalan sıralanmamıştır. Son adımda tüm dizi sıralıdır.
Uygulama Yer değiştir
swap_min(arr, i, min_idx) yaz. arr[i] ile arr[min_idx]'i değiştir, arr döndür. print(swap_min([3, 1, 2], 0, 1)) ile [1, 3, 2] yazdır.
Başlangıç kodu
def swap_min(arr, i, min_idx):
# İki elemanı değiştirÖrnek çözüm
def swap_min(arr, i, min_idx):
# İki elemanı değiştir
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
print(swap_min([3, 1, 2], 0, 1))Beklenen çıktı
[1, 3, 2]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Yer değiştirme
İki elemanı değiştir: arr[i], arr[min_idx] = ____İki elemanı değiştir: arr[i], arr[min_idx] = arr[min_idx]Açıklama: arr[min_idx] doğru.
2 Minimum bulma: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Swap |
Yer değiştir |
min_idx |
Minimum indeks |
O(1) |
Swap süresi |
n-1 |
Swap sayısı |
3 Yer değiştirme ne kadar sürer?
- O(log n) Doğru cevap
- O(n^2)
- O(n)
- O(1)
Açıklama: Yer değiştirme O(1)'dir.