Seçmeli Sıralama

Her geçişte en küçük elemanı bulup başa yerleştiren sıralama algoritması.

#Nasıl çalışır?

Seçmeli sıralama (selection sort), diziyi iki kısım olarak düşünür: solda sıralanmış kısım, sağda henüz sıralanmamış kısım. Başta sıralı kısım boştur.

Her geçişte sıralanmamış kısım baştan sona taranır ve en küçük eleman bulunur. Bu eleman, sıralanmamış kısmın ilk elemanıyla yer değiştirir; böylece sıralı kısım bir eleman büyür.

Bubble sort'tan farkı, her geçişte yalnızca bir kez yer değiştirme yapmasıdır. Karşılaştırma sayısı ise dizi sıralı olsa bile hep aynıdır.

#Canlı animasyon

$ selection_sort --visualizespace · ← → · r · sAdım 1/52

Her geçişte sıralanmamış kısmın en küçüğü bulunur ve başa yerleştirilir.

Hız

Karşılaştırma: 0Yer değiştirme: 0Şu anki minimumKarşılaştırılıyorYer değiştiriyorYerine oturdu

for i = 0 to n - 2
  min = i
  for j = i + 1 to n - 1
    if a[j] < a[min]: min = j
  swap(a[i], a[min])

#Adım adım

01Sıralanmamış kısmın ilk elemanını şimdilik minimum kabul et.
02Kalan elemanları tek tek bu minimumla karşılaştır; daha küçüğünü bulursan yeni minimum o olsun.
03Tarama bitince minimumu sıralanmamış kısmın ilk elemanıyla yer değiştir.
04Sıralı kısım bir eleman büyüdü; bir sonraki elemandan devam et.
05Sıralanmamış kısımda tek eleman kalınca dizi sıralanmıştır.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

def selection_sort(a: list[int]) -> None:
    n = len(a)
    for i in range(n - 1):
        # Find the smallest element of the unsorted part a[i:].
        smallest = i
        for j in range(i + 1, n):
            if a[j] < a[smallest]:
                smallest = j
        a[i], a[smallest] = a[smallest], a[i]


numbers = [5, 1, 4, 2, 8, 3]
selection_sort(numbers)
print(*numbers)

#Karmaşıklık

En iyi	O(n²)
Ortalama	O(n²)
En kötü	O(n²)
Ek bellek	O(1)
Kararlı mı?	Hayır
Yerinde mi?	Evet

Her durumda yaklaşık n²/2 karşılaştırma yapılır, çünkü minimumu bulmak için kalan elemanların hepsine bakmak gerekir. Buna karşılık en fazla n-1 yer değiştirme yapılır; yazma işleminin pahalı olduğu durumlarda bu bir avantajdır. Uzak elemanları yer değiştirdiği için kararlı değildir: eşit elemanların sırası bozulabilir.

#Ne zaman kullanılır?

Az sayıda yer değiştirme istendiğinde (örneğin belleğe yazmanın pahalı olduğu durumlarda) ya da çok küçük dizilerde kullanılabilir. Büyük veride ve kararlılık gerektiğinde merge sort veya insertion sort daha iyi bir seçimdir.