Yer değiştirme

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.

Örnek çözümü göster

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]))

Kendini test et

Yer değiştirme: kavramları eşleştir

Dış döngü

0'dan n-2'ye
İç arama

i'den n-1'e
Swap

n-1 kez
O(n^2)

Her zaman
Selection sort en iyi durumda kaç karşılaştırma yapar?
- n
- n(n-1)/2
- 1
- 0
Cevabı göster

n(n-1)/2 — En iyi durumda da n(n-1)/2 karşılaştırma yapar.

Dış döngü

Dış döngü ____ range(n - 1) ile döner.

Cevabı göster

Dış döngü for i in range(n - 1) ile döner.

Sıradaki ders: Özet - Selection sort

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler