Seçmeli sıralama
Seçmeli sıralama, bir listeyi birçok kişinin elindeki kartları sıraladığı gibi sıralar: en küçüğü bul, başa koy, sonra kalanların en küçüğünü bul. Çok karşılaştırma ama çok az takas yapar ve çalışma süresi listenin sırasına neredeyse hiç bağlı değildir.
Temel fikir
Listeyi solda başta boş olan sıralı bir kısma ve sağda sıralanmamış bir kısma ayırın. Sıralanmamış kısmı tarayın ve en küçük değerin nerede olduğunu aklınızda tutun. Bu değeri sıralanmamış ilk değerle takas edin: sıralı kısım bir büyüdü. Yalnızca bir değer kalana kadar tekrarlayın; o değer en büyüğü olmak zorundadır.
Bir örnek
5, 1, 4, 2, 8 listesini alın. İlk geçiş beş değerin hepsini tarar, en küçük olarak 1'i bulur ve onu 5 ile takas eder: 1, 5, 4, 2, 8. İkinci geçiş 5, 4, 2, 8'i tarar, 2'yi bulur ve onu 5 ile takas eder: 1, 2, 4, 5, 8. Üçüncü geçiş 4'ü, dördüncü geçiş de 5'i zaten yerinde bulur, bu yüzden hiçbir şey yer değiştirmez. Toplam 4 + 3 + 2 + 1 = 10 karşılaştırma ve yalnızca 2 takas. Kabarcık sıralaması aynı listede 4 takas gerektirir.
Karşılaştırma sayısı hep aynı
Hangi değerin en küçük olduğundan emin olmak için taramanın kalan her değere bakması gerekir. 1. geçiş n − 1 karşılaştırma, 2. geçiş n − 2 karşılaştırma yapar ve bu 1'e kadar böyle sürer; toplamı n(n − 1)/2 eder. Bu sayı listeye bağlı değildir: sıralı bir liste, ters sıralı bir liste kadar karşılaştırma gerektirir. Seçmeli sıralama erken duramaz, çünkü en küçük değeri zaten başta bulan bir tarama, geri kalanlar hakkında hiçbir şey öğrenmemiştir.
Az takas
Her geçiş en fazla bir takas yapar, bu yüzden seçmeli sıralama hiçbir zaman n − 1'den fazla takas yapmaz; en küçük değer zaten yerindeyse takası atlar. Kabarcık sıralaması ve eklemeli sıralama, sırası yanlış olan çift sayısı kadar takas yapar; bu da yaklaşık n²/2'ye kadar çıkabilir. Bir değeri yazmak iki değeri okumaktan çok daha pahalıysa, örneğin her yazmada yıpranan bellekte, az sayıda takas bir avantajdır.
Kararlı değil
Eşit değerler ilk sıralarını koruyorsa sıralama kararlıdır. Seçmeli sıralama kararlı değildir, çünkü uzak mesafeli bir takas bir değeri kendisine eşit bir değerin ötesine taşıyabilir. 2, 2, 1 listesinde ilk geçiş ilk 2'yi 1 ile takas eder ve 1, 2, 2 elde edilir; iki 2 artık ters sıradadır. Takas etmek yerine aradaki değerleri kaydıran bir sürüm kararlıdır, ama çok daha fazla değer taşır.
Kendiniz keşfedin
Uygulamayı açın ve Oynat'a basın ya da her seferinde bir karşılaştırma ilerlemek için Adım'a basın. Taranan değer vurgulanır, şimdiye kadarki en küçük değerin kendine ait bir rengi vardır ve her geçiş soldaki sıralı kısma bir takasla biter. Sıralı ve ters sıralı bir liste deneyin: karşılaştırmalar aynı çıkar, yalnızca takaslar farklıdır.
Sık sorulan sorular
Seçmeli sıralamanın zaman karmaşıklığı nedir?
Her durumda O(n²): n değer için, sıraları ne olursa olsun tam olarak n(n − 1)/2 karşılaştırma. En fazla n − 1 takas yapar ve yalnızca O(1) ek bellek gerektirir.
Seçmeli sıralama ile kabarcık sıralaması arasındaki fark nedir?
Kabarcık sıralaması ilerlerken komşuları takas eder ve bir geçişte hiç takas olmazsa erken durabilir. Seçmeli sıralama yalnızca en küçük değerin nerede olduğunu aklında tutar ve her geçişin sonunda bir takas yapar. Seçmeli sıralama daha az takas yapar; kabarcık sıralaması neredeyse sıralı listelerde daha hızlıdır.
Seçmeli sıralama kararlı mıdır?
Hayır. Bir takas, bir değeri kendisine eşit başka bir değerin ötesine taşıyabilir; böylece eşit değerlerin sırası değişebilir. Takas etmek yerine değerleri kaydırarak kararlı hâle getirilebilir, ancak bu daha fazla taşıma gerektirir.
Yığın sıralamasının seçmeli sıralamayla bağlantısı nedir?
Yığın sıralaması, bir sonraki değeri daha hızlı bulan bir seçmeli sıralamadır: sıralanmamış kısmı bir yığında tutar, böylece her seçim tam bir tarama yerine yaklaşık log n adım sürer. Bu da toplamı O(n log n)'ye indirir.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
Seçmeli sıralamayı deneyin