Sıralama algoritmaları karşılaştırması
Tek bir en hızlı sıralama algoritması yoktur. Bazıları basit ama yavaştır, bazıları rastgele verilerde hızlıdır ama sıralı verilerde tökezler, bazıları ise hiç karşılaştırmalı sıralama değildir. Sekizini aynı listede yarıştırmak farkları bir bakışta gösterir.
Üç aile
Kabarcık, seçmeli ve eklemeli sıralama basit sıralamalardır. Birbirine yakın değerleri karşılaştırıp takas ederler ve rastgele bir listede n² ile orantılı süreye ihtiyaç duyarlar. Birleştirmeli, hızlı ve yığın sıralaması işi akıllıca böler ve n log n ile orantılı süreye ihtiyaç duyar; bu, yalnızca iki değerden hangisinin büyük olduğunu sorabilen bir sıralamanın yapabileceğinin en iyisidir. Taban ve sayarak sıralama bu soruyu tamamen atlar: basamakları veya değerlerin kendisini kullanırlar; bu da yalnızca küçük tam sayılar gibi anahtarlarda işe yarar.
İşi ölçmek
Sıralama Yarışı her karşılaştırma, okunan her basamak veya değer ve her takas veya taşıma için bir işlem sayar. 40 rastgele değerde bu, sayarak sıralama için yaklaşık 120, taban sıralaması için 240, hızlı sıralama için 260, birleştirmeli sıralama için 380, yığın sıralaması için 490, seçmeli ve eklemeli sıralamanın her biri için yaklaşık 820 ve kabarcık sıralaması için 1.100'ün üzerinde eder. Gerçek bilgisayarlar belleği de önemser: listede ilerleme biçimleri nedeniyle hızlı sıralama pratikte genellikle sayacının gösterdiğinden daha hızlı, yığın sıralaması ise daha yavaştır.
Girdi önemlidir
Neredeyse sıralı bir listede eklemeli sıralama 40 değer için yalnızca yaklaşık 50 işleme, kabarcık sıralaması yaklaşık 90 işleme ihtiyaç duyar, çünkü her değer yerine yakındır. Ters bir listede aynı ikisi, en kötü durumları olan 1.560 işleme ihtiyaç duyar. Seçmeli, yığın, birleştirmeli, taban ve sayarak sıralama için sıra pek fark etmez. Üçün medyanını kullanan hızlı sıralama sıralı ve ters listelerle iyi başa çıkar, ama saf bir pivotla sıralı bir liste onun en kötü durumudur. Az sayıda farklı değer hızlı sıralamayı yavaşlatır, çünkü eşit değerlerin hepsi tek bir tarafa gider.
Bellek ve kararlılık
Kabarcık, seçmeli, eklemeli, hızlı ve yığın sıralaması yerinde çalışır; çok az ek bellek kullanır ya da hiç kullanmaz. Birleştirmeli, taban ve sayarak sıralama liste uzunluğunda bir tampona ihtiyaç duyar. Kararlı bir sıralama eşit değerleri özgün sıralarında tutar: kabarcık, eklemeli, birleştirmeli, taban ve sayarak sıralama kararlıdır; seçmeli, hızlı ve yığın sıralaması değildir. Kararlılık, kayıtları önce bir alana sonra başka bir alana göre sıraladığınızda önemlidir.
Hangisini kullanmalı
Pratikte programlama dilinizde yerleşik olan sıralamayı kullanırsınız. Bu genellikle Timsort'tur: kısa parçalar için eklemeli sıralamayı kullanan ve kısmen sıralı verilerde hızlı olan bir birleştirmeli sıralama. Ya da introsort'tur: gerektiğinde yığın sıralamasına geçen ve küçük parçalar için eklemeli sıralamayı kullanan bir hızlı sıralama. Çok sayıda küçük tam sayı anahtarında sayarak veya taban sıralaması ikisini de geçebilir. Kabarcık ve seçmeli sıralama çoğunlukla öğretim araçlarıdır.
Keşfedin
Sıralama Yarışı'nı açın ve Oynat'a basın. Her kulvar aynı listedeki bir sıralamadır; sağdaki sayı onun işlemlerini sayar ve sıralama bittiğinde kulvar yeşile döner. Neredeyse sıralı bir liste, ters bir liste ve az sayıda farklı değer deneyin ve bitiş sırasının değiştiğini izleyin. Her sıralamanın ayrıca kendi uygulaması vardır; orada onu adım adım, ayrıntılı olarak inceleyebilirsiniz.
Sık sorulan sorular
En hızlı sıralama algoritması hangisidir?
Genel verilerde ortalamada en hızlıları n log n ile hızlı sıralama ve birleştirmeli sıralamadır (ve introsort ile Timsort gibi bunların üzerine kurulu melez yöntemler). Küçük tam sayı anahtarlarında sayarak ve taban sıralaması daha da hızlıdır. Kısa veya neredeyse sıralı listelerde eklemeli sıralama kazanır.
Neden hiçbir karşılaştırmalı sıralama n log n'yi geçemez?
n değerli bir liste n! farklı sırada olabilir ve her karşılaştırmanın iki sonucu vardır; bu yüzden en kötü durumda hepsini birbirinden ayırmak için en az log₂(n!) karşılaştırma gerekir. Bu yaklaşık n log₂ n'dir. Taban ve sayarak sıralama karşılaştırma yapmadıkları için bu sınıra takılmaz.
Hangi sıralama algoritmaları kararlıdır?
Kabarcık, eklemeli, birleştirmeli, taban ve sayarak sıralama olağan biçimlerinde kararlıdır. Seçmeli sıralama, hızlı sıralama ve yığın sıralaması kararlı değildir, çünkü değerleri uzak mesafelere taşırlar.
Hangi sıralamalar ek bellek gerektirir?
Birleştirmeli, taban ve sayarak sıralama yaklaşık liste uzunluğunda bir tampon gerektirir. Kabarcık, seçmeli, eklemeli ve yığın sıralaması neredeyse hiç gerektirmez, hızlı sıralama ise özyineleme için yalnızca biraz gerektirir.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
Sıralama Yarışı'nı başlatın