Yer değiştirme
- Algoritmalar kursu
- Başlangıç
- Ders 27/80
- 4 dk
Minimimi başla yer değiştirmeyi ve tür sayısını öğrenirsin.
Tam selection sort
Selection sort'u tam uygulamak için dış döngü her konum için, iç arama o konumdan sonraki minimumu bulur ve yer değiştirir.
Dış döngü 0'dan n-2'ye, iç arama i'den n-1'e kadar gider. Her adımda bir minimum bulunur ve yer değiştirilir.
Karmaşıklık analizi
Selection sort'un karmaşıklığı her zaman O(n^2)'dir. En iyi, en kötü ve ortalama durumlar aynıdır çünkü her zaman tüm kalan elemanlar taranır.
Yer değiştirme sayısı en fazla n-1'dir, bu da bubble sort'tan daha azdır. Ama karşılaştırma sayısı her zaman n(n-1)/2'dir.
Uygulama Selection sort
selection_sort(arr) yaz. Her konumda minimum bul ve yer değiştir. print(selection_sort([64, 25, 12, 22, 11])) ile [11, 12, 22, 25, 64] yazdır.
Başlangıç kodu
def selection_sort(arr):
# Diziyi sıralaÖrnek çözüm
def selection_sort(arr):
# Diziyi sırala
n = len(arr)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
print(selection_sort([64, 25, 12, 22, 11]))Beklenen çıktı
[11, 12, 22, 25, 64]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Yer değiştirme: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Dış döngü |
0'dan n-2'ye |
İç arama |
i'den n-1'e |
Swap |
n-1 kez |
O(n^2) |
Her zaman |
2 Selection sort en iyi durumda kaç karşılaştırma yapar?
- n
- n(n-1)/2 Doğru cevap
- 1
- 0
Açıklama: En iyi durumda da n(n-1)/2 karşılaştırma yapar.
3 Dış döngü
Dış döngü ____ range(n - 1) ile döner.Dış döngü for i in range(n - 1) ile döner.Açıklama: for i in doğru.