Counting Sort ve Radix Sort

Kısaca: Counting sort ve radix sort karşılaştırmasız sıralar; bu yüzden anahtarlar küçük bir aralıktan tam sayılarsa O(n log n)‘den hızlı olabilir.

Biraz daha ayrıntılı: Quicksort gibi karşılaştırma tabanlı yöntemler hiçbir zaman O(n log n)‘den iyi olamaz. Anahtarların özelliklerinden yararlanmak bu sınırı aşar.

Ayrıntılı

• Counting sort: Her değerin kaç kez geçtiğini sayar (k boyutlu bir dizi), buradan başlangıç konumlarını çıkarır ve öğeleri oraya yazar. Çalışma süresi O(n + k), kararlı.
• Sınır: Değer aralığı k devasaysa (örneğin 64 bitlik sayılar), sayım dizisi kullanılamaz.
• Radix sort: Basamak basamak, en düşük basamaktan en yükseğe, her seferinde counting sort gibi kararlı bir yöntemle sıralar. d basamak ve b tabanı için çalışma süresi O(d · (n + b)).
• Örnek: 256 tabanında 32 bitlik sayılar: yalnızca dört geçiş.
• Kullanım: Kimlik numaralarını, posta kodlarını, sabit uzunluklu dizeleri sıralama, grafik boru hatları.
• Bedel: Ek bellek ve anahtar türüne bağımlılık.

Ayrıca bak: Büyük-O gösterimi, Sıralama