- Kullanılan kova
- Az önce taşınan
- Geri kopyalanan
- Yerinde
Taban sıralaması
Taban sıralaması, tam sayıları hiçbir zaman ikisini karşılaştırmadan sıralar. Listeyi önce birler basamağına, sonra onlar basamağına, sonra yüzler basamağına göre sıralar; her seferinde değerleri on kovaya taşır ve sırayla geri kopyalar. Listenin altındaki sırada kovaların her seferinde bir taşımayla dolmasını ve listenin giderek daha çok basamağa göre sıralanmasını izleyin. Sıralamayı izlemek için Oynat'a, her seferinde bir taşıma ilerlemek için Adım ve Geri'ye basın. Herhangi bir yere atlamak için adım kaydırıcısını sürükleyin. 0'dan 9'a kadar kovalar listenin altındaki sırada yan yana durur. Kutucuklar okunan rakamları, taşımaları ve geçişleri sayar. Çubuk sayısını ve başlangıç düzenini seçin ya da 999'a kadar kendi sayılarınızı yazın. Tahta seçiliyken ok tuşları adım atar, boşluk tuşu oynatır ve duraklatır, Home ve End başa ve sona atlar.
Nasıl çalışır
- Çubuk sayısını ve başlangıç düzenini seçin ya da yüzler geçişini de görmek için 999'a kadar kendi tam sayılarınızı yazın.
- Oynat'a basın ya da her seferinde bir değer taşımak için Adım ve Geri'yi kullanın. Sıralamanın herhangi bir yerine atlamak için adım kaydırıcısını sürükleyin.
- Her geçişi izleyin: rakamlar sayılır, her değer kendi kovasına taşınır, sonra kovalar geri kopyalanır.
Taban sıralaması nasıl çalışır
Her sayının yalnızca son basamağına bakın ve listeyi ona göre sıralayın: her sayıyı geliş sırasını koruyarak 0'dan 9'a kadar on kovadan birine koyun, sonra kovaları birbiri ardına geri kopyalayın. Aynısını onlar basamağıyla, sonra yüzler basamağıyla yapın. Her geçiş aynı rakamı paylaşan sayıların sırasını koruduğu için önceki geçişler bu sayıların kendi aralarındaki sırayı belirlemeye devam eder ve son geçişten sonra tüm liste sıralanmış olur.
Hiç karşılaştırma yok
Karşılaştırmalı sıralamalar, ne kadar akıllıca bir hile kullanırlarsa kullansınlar, en kötü durumda en az yaklaşık n log₂ n karşılaştırmaya ihtiyaç duyar. Taban sıralaması bunun yerine rakamları okuyarak bu sınıra takılmaz: her geçiş her değerin bir rakamını okur ve her değeri iki kez taşır; yani d basamak d geçiş gerektirir ve iş n · d ile büyür. Kısa anahtarlardan oluşan uzun listelerde bu karşılığını verir: 999'a kadar bir milyon sayı üç geçiş alır, oysa karşılaştırmalı bir sıralama yaklaşık 20 milyon karşılaştırma gerektirir. Bedeli, yalnızca rakam veya karakterlerden oluşan anahtarlarla çalışması ve kovalar için yer gerektirmesidir.
Sık sorulan sorular
Taban sıralaması nasıl çalışır?
Sayıları önce son basamaklarına, sonra ondan önceki basamağa göre sıralar ve bu, ilk basamağa kadar böyle sürer. Her geçiş sayıları sıralarını koruyarak o basamağa göre on kovaya koyar ve kovaları geri kopyalar. En anlamlı basamak için yapılan geçişten sonra liste sıralanmış olur.
Neden son basamakla başlanıyor?
Çünkü her geçiş kararlıdır: aynı rakama sahip sayılar önceki geçişlerin verdiği sırayı korur. Bu yüzden ilk basamak üzerindeki son geçiş sırayı belirler, eşitlikleri ise zaten sıralanmış basamaklar çözer. Buna LSD (least significant digit, en az anlamlı basamak) taban sıralaması denir.
Taban sıralaması quicksort'tan daha mı hızlı?
Çok sayıda kısa anahtarda olabilir: işi, değer sayısı çarpı basamak sayısı ile büyür, n log n yoktur. Az sayıda değerde, çok uzun anahtarlarda veya rakamlardan oluşmayan verilerde quicksort ve birleştirmeli sıralama genellikle daha hızlı ve daha basittir.
Sayma sıralamasıyla ilişkisi nedir?
Taban sıralamasının her geçişi, tek bir basamak üzerinde bir sayma sıralamasıdır: her rakamdan kaç değer olduğunu sayın, her kovanın nerede başladığını hesaplayın ve değerleri sırayla oraya taşıyın.
Sayılarım bir yere gönderiliyor mu?
Hayır. Sıralama tarayıcınızda çalışır ve son ayarlarınız bu tarayıcının yerel depolamasında kalı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.
Editöre Git