Taban sıralaması

Taban sıralaması, sıralama algoritmaları arasında sıra dışı olandır: iki değerden hangisinin büyük olduğunu hiç sormaz. Sayıları basamak basamak okur ve on kova kullanarak her seferinde bir basamağa göre sıralar. Fikir bilgisayarlardan eskidir: delikli kart sıralama makineleri böyle çalışırdı.

0'dan 9'a kadar etiketli on kovadan oluşan bir sıranın üzerinde bir listenin çubukları; bir değer son basamağının kovasına düşüyor
0'dan 9'a kadar etiketli on kovadan oluşan bir sıranın üzerinde bir listenin çubukları; bir değer son basamağının kovasına düşüyor

Fikir

Sayıları yalnızca birler basamağına göre sıralayın. Sonra onlar basamağına göre sıralayın, ama onlar basamağı aynı olan sayılar ilk geçişin verdiği sırada kalacak şekilde. Sonra yüzler basamağına göre, aynı şekilde. Son geçişten sonra liste sıralıdır: önce yüzler karar verir, yüzleri aynı olanlar zaten onlarına göre sıralıdır, onları da aynı olanlar birlerine göre.

Kovalarla bir geçiş

Her geçiş, 0'dan 9'a kadar her rakam için bir tane olmak üzere on kova kullanır. Listeyi baştan sona dolaşın ve her sayıyı kendi rakamının kovasına, orada zaten bulunan sayıların arkasına taşıyın. Sonra kovaları, 0 numaralı kovadan başlayarak sırayla listeye geri boşaltın. Sayıları liste sırasıyla taşımak ve kovanın arkasına eklemek, geçişi kararlı tutan şeydir. Uygulama önce her rakam için sayıları sayar; böylece kovalar tek bir sırada yan yana durabilir ve her biri bir öncekinin hemen ardından başlar: bu, tek bir basamak üzerinde sayma sıralamasıdır.

Bir örnek

170, 45, 75, 90, 802, 24, 2, 66 listesini alın. Birler basamağına göre: 170, 90, 802, 2, 24, 45, 75, 66. Onlar basamağına göre: 802, 2, 24, 45, 66, 170, 75, 90; onlar basamağı 0 olan 802 ve 2'nin ilk geçişteki sıralarını koruduğuna dikkat edin. Yüzler basamağına göre: 2, 24, 45, 66, 75, 90, 170, 802. Sekiz sayı üzerinde üç geçiş: 24 okunan rakam ve 48 taşıma, tek bir karşılaştırma bile yok.

Ne kadar hızlı?

Her geçiş her sayının bir rakamını okur ve her sayıyı iki kez taşır; yani d basamaklı n sayı için iş n · d ile büyür. Karşılaştırmalı bir sıralama en kötü durumda en az yaklaşık n log₂ n karşılaştırmaya ihtiyaç duyar, çünkü n! olası sırayı her seferinde bir evet-hayır sorusuyla birbirinden ayırması gerekir. Taban sıralaması bu sınıra bağlı değildir, çünkü böyle sorular hiç sormaz. Çok sayıda kısa anahtarda, örneğin 1.000'in altındaki bir milyon sayıda, üç geçiş, karşılaştırmalı bir sıralamanın gerektireceği yaklaşık 20 milyon karşılaştırmadan çok daha az iştir. Uzun anahtarlarda veya az sayıda değerde bu avantaj kaybolur.

LSD ile MSD ve tarihçe

Burada gösterilen sürüm en az anlamlı basamakla (LSD) başlar. Tersi, yani önce en anlamlı basamak (MSD), listeyi ilk basamağa göre kovalara böler ve her kovayı ayrı sıralar; bu da farklı uzunluktaki dizgiler için uygundur. Taban sıralaması, Herman Hollerith'in 1890 ABD nüfus sayımı için yaptığı tablolama makinelerinin ardından gelen delikli kart sıralayıcılarına dayanır: bir sıralayıcı her kartı bir sütundaki deliğe göre on cepten birine düşürürdü ve operatörler desteyi sondan başlayarak her sütun için bir kez makineden geçirirdi.

Computer History Museum’daki bir Hollerith delikli kart tabülatörü, 1890 ABD nüfus sayımında kullanılan türden. Operatörler bir desteyi her sütun için bir kez sıralayıcıdan geçirirdi; bu, taban sıralamasının atasıdır.
Computer History Museum’daki bir Hollerith delikli kart tabülatörü, 1890 ABD nüfus sayımında kullanılan türden. Operatörler bir desteyi her sütun için bir kez sıralayıcıdan geçirirdi; bu, taban sıralamasının atasıdır.

Keşfedin

Uygulamayı açın ve Adım'a basın. Her geçiş önce rakamları sayar; bu, listenin altındaki sırada 0'dan 9'a kadar kovaların yerini belirler. Sonra sayılar, etkin kova vurgulanırken tek tek kovalarına düşer ve geri kopyalanır. Üç geçişin hepsini görmek için yukarıdaki örnek gibi 999'a kadar kendi sayılarınızı yazın.

Sık sorulan sorular

Taban sıralamasının zaman karmaşıklığı nedir?

Sabit bir tabanda d basamaklı n anahtar için O(n · d), artı her geçişteki kovaların maliyeti. Kovaların bulunduğu tampon için O(n) ek bellek gerektirir.

Taban sıralaması kararlı mıdır?

LSD taban sıralaması kararlı olmak zorundadır: yalnızca her geçiş aynı rakama sahip değerleri geldikleri sırada tuttuğu için çalışır. Bu yüzden sonuç da kararlıdır.

Taban sıralaması negatif sayıları veya ondalık sayıları sıralayabilir mi?

Doğrudan değil, ama bir hileyle olur: negatif sayıları hepsi pozitif olacak şekilde kaydırın ya da onları ayrı sıralayıp ters çevirin. Kayan noktalı sayılar küçük bir dönüşümden sonra bit desenlerine göre sıralanabilir.

Neden 10 tabanı?

Çünkü takip etmesi kolaydır. Bilgisayarlar genellikle her seferinde 8 veya 16 bite göre sıralar; böylece 32 bitlik bir sayı, 256 veya 65.536 kovayla dört ya da iki geçiş alı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.

Taban sıralamasını deneyin