Sayarak sıralama
Sayarak sıralama, değerleri hiç karşılaştırmadan sıralar. Her değerin, diyelim ki 1 ile 40 arasında bir tam sayı olduğunu biliyorsanız, her birinden kaç tane olduğunu sayabilir ve bu sayımlardan her birinin nereye ait olduğunu çıkarabilirsiniz. Küçük bir aralıkta bu, sıralamanın olabileceği kadar hızlıdır.
Sayma
En küçük ve en büyük değeri bulun ve aradaki her değer için, hepsi sıfırdan başlayan birer sayaç oluşturun. Listeyi baştan sona bir kez okuyun ve gördüğünüz her değerin sayacına bir ekleyin. Sayaçlar artık bir histogram oluşturur: kaç tane 1, kaç tane 2 ve böyle devam eder. n değer ve k sayaçla bu n adım sürer.
Toplama
En küçük değere eşit değerler önce gelir, bu yüzden blokları 1. yerde başlar. Sonraki değerin bloğu hemen onlardan sonra başlar ve böyle devam eder: her blok, kendinden önceki tüm sayımların toplamından sonra başlar. Önek toplamları denen bu birikimli toplamlar, histogramı sıralı listenin bir haritasına dönüştürür. Bu k adım sürer.
Yerleştirme
Listeyi ikinci kez okuyun ve her değeri bloğundaki bir sonraki boş yere taşıyın. Değerler listede göründükleri sırayla taşındığı için eşit değerler özgün sıralarını korur: sayarak sıralama kararlıdır. Tamponu geri kopyalayın; liste sıralanmıştır. Uygulama, değerleri yerleştirildikçe her sayacın yeniden azaldığını gösterir.
Bir örnek
4, 1, 3, 4, 2, 1, 4 listesini alın. 1'den 4'e kadar sayaçlar sırasıyla 2, 1, 1 ve 3 olur. Toplama blokları verir: 1'ler 1. ve 2. yerde, 2 3. yerde, 3 4. yerde ve 4'ler 5. ile 7. yerler arasında. Değerleri liste sırasıyla yerleştirmek 1, 1, 2, 3, 4, 4, 4 sonucunu verir: 7 değer sayıldı, 14 taşıma yapıldı, 4 sayaç kullanıldı ve hiç karşılaştırma yapılmadı.
Ne zaman kullanılır
Toplam iş n + k ile büyür. k, n'ye göre küçük olduğunda, örneğin 0 ile 100 arasındaki bin sınav puanında, sayarak sıralama yaklaşık n log₂ n karşılaştırma gerektiren her karşılaştırmalı sıralamadan daha hızlıdır. Aralık genişse savurgandır: bir milyona kadar dağılmış birkaç değer bir milyon sayaç gerektirir. Taban sıralaması (radix sort) bunu, sayarak sıralamayı her basamak için bir kez çalıştırarak çözer; böylece her geçiş yalnızca on sayaç gerektirir. Harold Seward, sayarak sıralamayı taban sıralamasıyla birlikte 1954'te tanımladı.
Keşfedin
Uygulamayı açın ve Adım'a basın. Liste ile tampon satırı arasındaki şerit, her değer için bir sayaç gösterir. Liste okunurken sayaçların dolduğunu, sayımlar toplandığında blokların tamponda belirdiğini ve değerler yerleştirildikçe sayaçların yeniden azaldığını izleyin. Büyük bloklar görmek için az farklı değer seçin ya da geniş bir aralığın kaç sayaç gerektirdiğini görmek için birbirinden uzak sayılar yazın.
Sık sorulan sorular
Sayarak sıralamanın zaman karmaşıklığı nedir?
n değer ve k olası değer için O(n + k); sayaçlar ve tampon için de O(n + k) ek bellek.
Sayarak sıralama neden her zaman en hızlısı değil?
Çünkü maliyeti yalnızca değerlerin sayısına değil, aralığına da bağlıdır. Aralık listeden çok daha büyükse sayaçların çoğu sıfırda kalır ve zaman ile bellek boşa gider.
Sayarak sıralama negatif sayılarla çalışabilir mi?
Evet. Sayaçlar en küçük değerden en büyüğe gider; bir sayacın indisini bulmak için en küçük değeri çıkarın. Uygulama da aynısını yapar.
Sayarak sıralama kararlı mıdır?
Evet, değerler liste sırasıyla bloklarındaki bir sonraki boş yere taşındığı sürece. Taban sıralaması buna dayanır.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
Sayarak sıralamayı deneyin