Seçim Sıralaması Nasıl Kullanılır

Seçimli sıralama, bir liste öğesini seçen ve ardından onun yerini başka bir öğeyle değiştiren bir sıralama tekniğidir. En büyük öğeyi seçer ve ardından onu listenin en yüksek dizinindeki bir öğeyle değiştirir.

Algoritma, liste sıralanana kadar bunu tekrar tekrar yapar. Seçimli sıralamanın nasıl çalıştığından tam olarak emin değilseniz doğru yere geldiniz. Aşağıda size bir örnek göstererek daha derinlemesine açıklayacağız.

Seçim Sıralaması: Yakından Bakış

Diyelim ki listeniz var: [39, 82, 2, 51, 30, 42, 7]. Listeyi seçim sıralamasını kullanarak sıralamak için önce listedeki en yüksek sayıyı bulmanız gerekir.

Verilen liste ile bu sayı 82'dir. 82'yi en yüksek dizindeki sayıyla değiştirin (yani, 7).

İlk geçişten sonra yeni liste sırası şöyle olacaktır: [39, 7, 2, 51, 30, 42, 82]. Algoritma tüm listeden her geçtiğinde buna "geçti" denir.

Sıralama işlemi sırasında listenin sıralanmış bir alt liste ve sıralanmamış bir alt liste tuttuğuna dikkat edin.

İlişkili: Big-O Notasyonu Nedir?

Orijinal liste, sıralanmış bir sıfır öğe listesi ve tüm öğelerin sıralanmamış bir listesi ile başlar. Ardından, ilk geçişten sonra, yalnızca 82 numaralı sıralanmış bir listeye sahiptir.

İkinci geçişte, sıralanmamış alt listedeki en yüksek sayı 51 olacaktır. Bu numara 42 ile değiştirilerek aşağıdaki yeni liste sırasını verir:

[39, 7, 2, 42, 30, 51, 82].

Tüm liste sıralanana kadar işlem tekrarlanır. Aşağıdaki şekil tüm süreci özetlemektedir:

Koyu siyah sayılar o andaki en yüksek liste değerini gösterir. Yeşil olanlar sıralanmış alt listeyi gösterir.

Algoritma Analizi

Bu algoritmanın karmaşıklığını (Big-O notasyonunu kullanarak) elde etmek için aşağıdaki adımları izleyin:

İlk geçişte (n-1) karşılaştırmaları yapılır. İkinci geçişte, (n-2). Üçüncü geçişte, (n-3) ve sadece bir karşılaştırma yapan (n-1)'inci geçişe kadar böyle devam eder.

Karşılaştırmaları aşağıdaki gibi özetlemek şunları verir:

(n-1)+ (n-1)+ (n-1)+...+1 = ((n-1)n)/2.

Bu nedenle seçim sıralaması O(n²).

Kod Uygulaması

Kod, Python ve Java kullanarak seçim sıralaması yapmak için kullanabileceğiniz işlevleri gösterir.

Python:

def seçimSırala (mylist):
x aralığında (len (mylist) - 1, 0, -1):
max_idx = 0
(1, x + 1) aralığındaki posn için:
listem[konum] > listem[max_idx] ise:
max_idx = konum
sıcaklık = listem[x]
listem[x] = listem[max_idx]
listem[max_idx] = sıcaklık

Java:

geçersiz seçimSırala (int my_array[]){ 
for (int x = 0; x < dizim.uzunluk - 1; x++) 
{ 
int dizin = x; 
for (int y = x + 1; y < dizim.uzunluk; y++){ 
if (my_array[y] < my_array[index]){ 
indeks = y; // en düşük dizini bul 
} 
} 
int temp = my_array[indeks]; // temp geçici bir depolamadır
my_array[index] = my_array[x]; 
my_array[x] = sıcaklık; 
}}

Seçim Sıralamasından Birleştirme Sıralamasına Geçiş

Yukarıdaki algoritma analizinin gösterdiği gibi, seçim sıralama algoritması O(n²). Üstel bir karmaşıklığa sahiptir ve bu nedenle çok büyük veri kümeleri için verimsizdir.

Kullanılacak çok daha iyi bir algoritma, O(nlogn) karmaşıklığına sahip birleştirme sıralaması olacaktır. Ve artık seçimle sıralamanın nasıl çalıştığını biliyorsunuz, sıralama algoritmaları için çalışma listenizin bir sonraki adımı birleştirme sıralaması olmalıdır.

Yazar hakkında