Sayarak Sıralama

Sıralama O(n + k) O(n + k)

Her değerin kaç kez geçtiğini sayar, sayımları önek toplamıyla son konumlara çevirir, sonra her elemanı doğrudan yerleştirir — karşılaştırmasız.

Boşta

8 eleman üzerinde Counting Sort başlıyor.

Değişmezcounts[v], v'nin şimdiye kadar kaç kez görüldüğüdür — hiç karşılaştırma yapılmaz.

1/37

karşılaştırma0hareket0sondaj0max0i0

karşılaştırtakaskaydırseçsıralı

counting-sort.c

void countingSort(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > max) max = arr[i];
 
    int count[max + 1];
    for (int i = 0; i <= max; i++) count[i] = 0;
 
    for (int i = 0; i < n; i++)
        count[arr[i]]++;
 
    for (int i = 1; i <= max; i++)
        count[i] += count[i - 1];
 
    int out[n];
    for (int i = n - 1; i >= 0; i--)
        out[--count[arr[i]]] = arr[i];
 
    for (int i = 0; i < n; i++)
        arr[i] = out[i];
}

Sayarak Sıralama nasıl çalışır?

Her değerin kaç kez geçtiğini say, sayımları önek toplamıyla son konumlara çevir, sonra kararlılık için sağdan tarayarak her elemanı doğrudan yerine koy.

En iyi durum

Her zaman O(n + k) — birkaç doğrusal geçiş.

En kötü durum

Dev değer aralığı k baskın çıkar: k boyutlu sayım dizisi ayrılıp taranmalı.

Ne zaman kullanılır?

Küçük ve bilinen aralıktan tamsayı anahtarlar; radix sıralamanın kararlı geçişi.