Sayma Sıralaması (Counting Sort)

#Nasıl çalışır?

Sayma sıralaması (counting sort) elemanları birbiriyle hiç karşılaştırmaz. Bunun yerine her değerden kaç tane olduğunu sayar.

Sayımlar birikimli toplanınca her değerin çıktıda nerede başlayacağı belli olur. Örneğin 3'ten küçük 5 değer varsa ilk 3, 5 numaralı yere gider. Elemanlar sonra soldan sağa gezilip doğrudan yerlerine konur.

Değer aralığı (k) küçükse doğrusal zamanda çalışır; karşılaştırmalı sıralamaların O(n log n) alt sınırına takılmaz. Eşit değerlerin sırasını korur, yani kararlıdır.

#Canlı animasyon

for each value v in a: count[v] = count[v] + 1
start[v] = how many values are smaller than v   // prefix sums
for each value v in a (left to right):
  output[start[v]] = v; start[v] = start[v] + 1
a = output

#Adım adım

1. 01Her değerden kaç tane olduğunu say.
2. 02Sayımları birikimli topla: her değerin çıktıda başlayacağı yer bulunur.
3. 03Diziyi soldan sağa gez; her elemanı kendi değerinin sıradaki yerine koy.
4. 04O değerin yer sayacını bir artır.
5. 05Çıktıyı diziye geri kopyala.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

def counting_sort(a: list[int]) -> list[int]:
    """Sorts non-negative integers without comparing elements. Stable."""
    if not a:
        return a
    count = [0] * (max(a) + 1)
    for v in a:
        count[v] += 1
    # Running totals: count[v] becomes the slot just after the last v.
    for v in range(1, len(count)):
        count[v] += count[v - 1]
    output = [0] * len(a)
    # Walk from the right so equal values keep their order.
    for v in reversed(a):
        count[v] -= 1
        output[count[v]] = v
    return output


print(*counting_sort([4, 2, 2, 8, 3, 3, 1]))

#Karmaşıklık

n eleman sayısı, k değer aralığıdır (en büyük − en küçük + 1). k, n'e göre küçükse doğrusal zamanda çalışır. Değerler çok geniş bir aralıktaysa (örneğin 1 ile 1 milyar arası) sayım dizisi devasa olur ve algoritma kullanışsızlaşır.

#Ne zaman kullanılır?

Küçük aralıktaki tam sayıları sıralarken (yaşlar, notlar, 0–255 arası piksel değerleri) çok hızlıdır. Radix sort'un her basamak turunda yardımcı algoritma olarak kullanılır. Ondalık sayılar ya da geniş aralıklar için uygun değildir.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.

#Bundan sonra

Bu dersi bildiğini varsayan dersler:

• Taban Sıralaması (Radix Sort)