Time and Space Complexity

Zaman Karmaşıklığı:

• O(n + k)
  • burada n eleman sayısı ve k değer aralığıdır (max + 1). Saymak için bir geçiş, yeniden oluşturmak için sayımlar üzerinden bir geçiş yapılır.
• k küçük ve sabit olduğunda, bu etkili bir şekilde O(n) olur ve karşılaştırmalı sıralamaların O(n log n) karmaşıklığından daha hızlıdır.

Alan Karmaşıklığı:

• O(n + k)
  • Sayım dizisi O(k) ve çıktı O(n) kullanır.

Özet:

• Counting Sort (Sayım Sıralaması), küçük tam sayı aralıkları için doğrusal zamanda çalışan kararlı, karşılaştırmalı olmayan bir sıralama algoritmasıdır.
• Değer aralığı k çok büyük olduğunda uygun bir seçenek değildir, çünkü sayım dizisi devasa olacaktır. Bu sürüm negatif olmayan tam sayıları varsayar.