Sayma Sıralaması Algoritması Nedir?
Sayma Sıralaması, belirli bir aralıktaki tam sayıları sıralamak için kullanılan doğrusal zamanlı bir sıralama algoritmasıdır. Özellikle anahtar değerlerinin dağılımı bilindiğinde oldukça verimlidir.
Sayma Sıralaması, her bir elemanın kaç kez tekrarlandığını sayarak ve ardından bu sayımları kullanarak sıralanmış diziyi oluşturarak çalışır. Belirli bir aralıktaki tam sayılar için etkilidir.
Adım adım çözümlü örnekler
Örnek Dizi: [4, 2, 2, 8, 3, 3, 1]
1. Maksimum değeri bul: 8. 2. Her sayının kaç kez geçtiğini say: 1 (bir kez), 2 (iki kez), 3 (iki kez), 4 (bir kez), 8 (bir kez). 3. Sayım dizisini oluştur: [1, 2, 2, 1, 0, 0, 0, 1]. 4. Kümülatif toplamları hesapla: [1, 3, 5, 6, 6, 6, 6, 7]. 5. Sıralanmış diziyi oluştur: [1, 2, 2, 3, 3, 4, 8].
Dizi: [5, 1, 4, 1, 5, 9, 2, 6]
1. Maksimum değer: 9. 2. Sayımlar: 1(2), 2(1), 4(1), 5(2), 6(1), 9(1). 3. Sayım dizisi: [0, 2, 1, 0, 1, 2, 1, 0, 0, 1]. 4. Kümülatif toplam: [0, 2, 3, 3, 4, 6, 7, 7, 7, 8]. 5. Sıralanmış dizi: [1, 1, 2, 4, 5, 5, 6, 9].
Bilgi kartları
Mini test
S1.Sayma Sıralaması algoritması için en uygun veri türü hangisidir?
S2.Eğer sıralanacak dizideki en büyük eleman 1000 ise ve dizide 10 eleman varsa, Sayma Sıralaması'nın 'k' değeri ne olur?
S3.Sayma Sıralaması'nın zaman karmaşıklığı O(n+k) olması ne anlama gelir?
Sık yapılan hatalar
Sayma Sıralaması, her zaman O(n log n) karmaşıklığında çalışır. — Doğrusu: Sayma Sıralaması, O(n+k) karmaşıklığında çalışır ve k'nın n'ye göre küçük olması durumunda O(n) olabilir.
Sadece negatif tam sayılar için kullanılabilir. — Doğrusu: Genellikle negatif olmayan tam sayılar için kullanılır, ancak aralık ayarlanarak negatif sayılar da dahil edilebilir.
Sıkça sorulan sorular
Sayma Sıralaması kararlı mıdır?
Evet, eğer eşit anahtarlara sahip elemanların orijinal sıralaması korunarak yerleştirilirse kararlıdır.
Sayma Sıralaması'nın hafıza kullanımı nasıldır?
O(k) ek hafıza gerektirir, bu da anahtar aralığı büyük olduğunda bir dezavantaj olabilir.
Sayma Sıralaması hangi durumlarda tercih edilmelidir?
Anahtar aralığının (k) eleman sayısına (n) göre çok büyük olmadığı ve sıralanacak verilerin tam sayılar olduğu durumlarda tercih edilir.