Sayma Sıralama Algoritması Açıklaması

Sayma Sıralama, giriş dizisindeki her bir değerin kaç kez göründüğünü sayarak tamsayıları sıralayan, karşılaştırma tabanlı olmayan bir sıralama algoritmasıdır. Elemanları birbiriyle karşılaştırmak yerine, frekansları kaydetmek için bir sayım dizisi kullanır ve ardından sıralanmış sonucu yeniden oluşturur.

Sayma Sıralama, değer aralığı çok büyük olmadığında çok hızlı olabilir. Zaman karmaşıklığı O(n + k)'dir; burada n, eleman sayısı ve k, olası değerlerin aralığıdır. Bu özelliği onu Kabarcık Sıralaması, Seçmeli Sıralama, Eklemeli Sıralama, Birleştirmeli Sıralama ve Hızlı Sıralama gibi karşılaştırma tabanlı algoritmalardan ayırır.

Giriş

Çoğu başlangıç seviyesi sıralama algoritması, değerleri karşılaştırarak çalışır. Kabarcık Sıralaması komşu elemanları karşılaştırır, Seçmeli Sıralama en küçük değeri arar, Eklemeli Sıralama mevcut değeri önceki değerlerle karşılaştırır ve Hızlı Sıralama elemanları bir pivot ile karşılaştırır.

Sayma Sıralama farklı bir fikir kullanır. Bir elemanın diğerinden defalarca daha büyük veya daha küçük olup olmadığını sormaz. Bunun yerine, her bir değerin kaç kez geçtiğini sayar ve ardından bu sayımları kullanarak değerleri sıralı bir düzende yerleştirir.

Bu, Sayma Sıralamayı, 0'dan 100'e kadar sınav puanları, yaşlar, küçük kimlikler, derecelendirmeler veya tekrarlayan sayısal kategoriler gibi sınırlı bir aralık içindeki tamsayıları sıralarken özellikle kullanışlı kılar.

Sayma Sıralaması Nedir?

Sayma Sıralama, tamsayı değerleri için tasarlanmış bir sıralama algoritmasıdır. Bir sayım dizisi veya frekans dizisi adı verilen ek bir dizi oluşturarak çalışır. Bu sayım dizisindeki her dizin, giriş dizisinden olası bir değeri temsil eder.

Giriş dizisindeki her sayı için algoritma, o sayının sayımını artırır. Tüm değerler sayıldıktan sonra, algoritma her bir değeri kaç kez göründüğüne göre yerleştirerek sıralanmış diziyi yeniden oluşturur.

Ana fikir basittir:

  • Dizideki değer aralığını bulun.

  • Bir sayım dizisi oluşturun.

  • Her bir değerin kaç kez göründüğünü sayın.

  • Sıralanmış çıktıyı yeniden oluşturmak için sayım dizisini kullanın.

Sayma Sıralama, frekansları saymak algoritmanın ana işlemi olduğu için "sayma" olarak adlandırılır.

Sayma Sıralaması Neden Farklıdır

Sayma Sıralama, karşılaştırma tabanlı olmadığı için birçok yaygın sıralama algoritmasından farklıdır. Bu, eleman çiftlerini tekrar tekrar karşılaştırarak sıralama yapmadığı anlamına gelir.

Örneğin, Hızlı Sıralama şu tür sorular sorar:

Is this value less than or equal to the pivot?

Eklemeli Sıralama şu tür sorular sorar:

Is the previous value greater than the current value?

Sayma Sıralama farklı bir soru sorar:

How many times did this value appear?

Bu fark, değer aralığı yeterince küçük olduğunda Sayma Sıralamanın doğrusal benzeri bir performans elde etmesini sağlar.

Sayma Sıralaması En İyi Ne Zaman Çalışır

Sayma Sıralama, giriş değerleri tamsayı olduğunda ve olası değerlerin aralığı sınırlı olduğunda en iyi şekilde çalışır.

Örneğin, Sayma Sıralama şunlar için uygundur:

  • 0 ile 100 arasındaki sınav puanlarını sıralama.

  • Küçük bir aralıktaki yaşları sıralama.

  • 1'den 5'e kadar ürün derecelendirmelerini sıralama.

  • Küçük kategori ID'lerini sıralama.

  • Tekrarlanan tamsayı değerlerini sıralama.

Sayma Sıralama, aralık eleman sayısına kıyasla çok büyük olduğunda uygun değildir. Örneğin, değerleri 0 ile 1.000.000 arasında olabilen sadece 10 sayıyı sıralamak çok fazla bellek israfına neden olabilir.

Sayma Sıralaması Adım Adım Nasıl Çalışır

Sayma Sıralama öncelikle basit bir versiyon kullanılarak açıklanabilir. Bu versiyon frekansları sayar ve ardından sıralanmış diziyi doğrudan yeniden oluşturur.

Algoritma şu adımları takip eder:

  1. Giriş dizisindeki maksimum değeri bulun.

  2. Maksimum değer + 1 boyutunda bir sayım dizisi oluşturun.

  3. Tüm sayım değerlerini sıfıra ayarlayın.

  4. Giriş dizisini döngüleyerek her bir değeri sayın.

  5. Sayım dizisini döngüleyerek her bir değeri frekansına göre geri yazın.

Bu basit versiyonun anlaşılması kolaydır ve sadece sıralanmış sayılara ihtiyacımız olduğunda iyi çalışır. Stabil bir versiyon, kümülatif sayımlar ve bir çıktı dizisi kullanır, bunu daha sonra açıklayacağız.

Manuel Çalıştırma Örneği

Aşağıdaki diziyi Sayma Sıralaması kullanarak manuel olarak sıralayalım:

[4, 2, 2, 8, 3, 3, 1]

En küçük değer 1 ve en büyük değer 8'dir. Basit versiyon için, 0'dan 8'e kadar bir sayım dizisi oluştururuz.

Value:  0 1 2 3 4 5 6 7 8
Count:  0 0 0 0 0 0 0 0 0

Adım 1: Frekansları Sayın

Şimdi giriş dizisindeki her bir değeri okuyup sayımını artırıyoruz.

İlk değer 4:

Value:  0 1 2 3 4 5 6 7 8
Count:  0 0 0 0 1 0 0 0 0

Sonraki değer 2:

Value:  0 1 2 3 4 5 6 7 8
Count:  0 0 1 0 1 0 0 0 0

Sonraki değer tekrar 2:

Value:  0 1 2 3 4 5 6 7 8
Count:  0 0 2 0 1 0 0 0 0

Sonraki değer 8:

Value:  0 1 2 3 4 5 6 7 8
Count:  0 0 2 0 1 0 0 0 1

Sonraki değer 3:

Value:  0 1 2 3 4 5 6 7 8
Count:  0 0 2 1 1 0 0 0 1

Sonraki değer tekrar 3:

Value:  0 1 2 3 4 5 6 7 8
Count:  0 0 2 2 1 0 0 0 1

Son değer 1:

Value:  0 1 2 3 4 5 6 7 8
Count:  0 1 2 2 1 0 0 0 1

Bu şu anlama gelir:

  • 1 değeri bir kez görünür.

  • 2 değeri iki kez görünür.

  • 3 değeri iki kez görünür.

  • 4 değeri bir kez görünür.

  • 8 değeri bir kez görünür.

Adım 2: Sıralı Diziyi Yeniden Oluşturun

Şimdi sayım dizisini soldan sağa okuyoruz. Her dizin için, o dizini sayım sayısı kadar sonuca yazıyoruz.

0. dizinin sayımı 0, bu yüzden hiçbir şey yazmıyoruz.

1. dizinin sayımı 1, bu yüzden 1 yazıyoruz:

[1]

2. dizinin sayımı 2, bu yüzden 2'yi iki kez yazıyoruz:

[1, 2, 2]

3. dizinin sayımı 2, bu yüzden 3'ü iki kez yazıyoruz:

[1, 2, 2, 3, 3]

4. dizinin sayımı 1, bu yüzden 4 yazıyoruz:

[1, 2, 2, 3, 3, 4]

5, 6 ve 7. dizinlerin sayımı 0, bu yüzden hiçbir şey yazmıyoruz.

8. dizinin sayımı 1, bu yüzden 8 yazıyoruz:

[1, 2, 2, 3, 3, 4, 8]

Nihai Sıralanmış Dizi

[1, 2, 2, 3, 3, 4, 8]

Bu manuel çalıştırma, Sayma Sıralamasının temel fikrini gösterir. Algoritma, değerleri birbiriyle karşılaştırmak yerine sayarak sıraladı.

Sayma Sıralama Algoritması Adımları

Basit Sayma Sıralama algoritması şöyle açıklanabilir:

  1. Dizideki maksimum değeri bulun.

  2. 0'dan maksimum değere kadar bir sayım dizisi oluşturun.

  3. Her giriş değerinin oluşum sayısını sayın.

  4. Boş bir sonuç dizisi oluşturun.

  5. Sayım dizisindeki her değer için, değeri sayımına göre ekleyin.

  6. Sıralanmış sonucu döndürün.

Bu sürümün uygulanması kolaydır, ancak nesneleri veya kayıtları sıralarken her zaman stabil değildir. Stabil sıralama için kümülatif sayımlar gereklidir.

Basit Sayma Sıralaması İçin Sözde Kod

countingSort(array):
    max = find maximum value in array

    count = array of size max + 1 filled with 0

    for each value in array:
        count[value] = count[value] + 1

    result = empty array

    for value from 0 to max:
        while count[value] > 0:
            append value to result
            count[value] = count[value] - 1

    return result

Bu sözde kod, negatif olmayan tamsayılar için çalışır. Dizi negatif sayılar içeriyorsa, daha sonra açıklanacak olan bir ofset kullanmamız gerekir.

PHP'de Sayma Sıralaması Örneği

İşte negatif olmayan tamsayılar için basit bir PHP Sayma Sıralaması uygulaması:

<?php

function countingSort(array $numbers): array
{
    if ($numbers === []) {
        return [];
    }

    $max = max($numbers);
    $count = array_fill(0, $max + 1, 0);

    foreach ($numbers as $number) {
        $count[$number]++;
    }

    $sorted = [];

    for ($value = 0; $value <= $max; $value++) {
        while ($count[$value] > 0) {
            $sorted[] = $value;
            $count[$value]--;
        }
    }

    return $sorted;
}

$numbers = [4, 2, 2, 8, 3, 3, 1];

print_r(countingSort($numbers));

Çıktı şöyle olacaktır:

Array
(
    [0] => 1
    [1] => 2
    [2] => 2
    [3] => 3
    [4] => 3
    [5] => 4
    [6] => 8
)

Bu uygulama doğrudan ve okunması kolaydır. Her sayıyı sayar, ardından frekans dizisine göre sıralanmış sonucu oluşturur.

JavaScript'te Sayma Sıralaması Örneği

Aynı algoritmanın JavaScript'te uygulanmış hali:

function countingSort(numbers) {
    if (numbers.length === 0) {
        return [];
    }

    const max = Math.max(...numbers);
    const count = new Array(max + 1).fill(0);

    for (const number of numbers) {
        count[number]++;
    }

    const sorted = [];

    for (let value = 0; value <= max; value++) {
        while (count[value] > 0) {
            sorted.push(value);
            count[value]--;
        }
    }

    return sorted;
}

const numbers = [4, 2, 2, 8, 3, 3, 1];

console.log(countingSort(numbers));

Çıktı şöyle olacaktır:

[1, 2, 2, 3, 3, 4, 8]

JavaScript versiyonu, PHP versiyonuyla aynı mantığı takip eder. Sayım dizisi frekansları saklar ve sıralanmış dizi sayım değerlerinden yeniden oluşturulur.

Stabil Sayma Sıralaması

Sayma Sıralamasının basit versiyonu, düz sayıları sıralamak için yeterlidir. Ancak, kayıtları veya nesneleri sıralarken stabilite önem kazanır.

Stabil bir sıralama algoritması, eşit elemanların göreceli sırasını korur. Örneğin, puanları olan öğrencilerimiz olduğunu varsayalım:

Ali: 90
Sara: 80
Omar: 90
Lina: 70

Eğer puana göre sıralarsak ve algoritma stabil ise, Ali hala Ömer'den önce görünmelidir çünkü her ikisi de aynı puana sahiptir ve Ali orijinal listede ilk sırada yer almıştır.

Stabil Sayma Sıralaması, her elemanın nihai konumunu belirlemek için kümülatif sayımları kullanır.

Kümülatif Sayım Nedir?

Kümülatif sayım, belirli bir değere eşit veya ondan küçük kaç eleman olduğunu gösterir. Her bir sayım değerinin önceki sayım değerine eklenmesiyle oluşturulur.

Manuel örnekteki frekans dizisini düşünelim:

Value:  0 1 2 3 4 5 6 7 8
Count:  0 1 2 2 1 0 0 0 1

Şimdi bunu kümülatif sayıma dönüştürüyoruz:

Value:       0 1 2 3 4 5 6 7 8
Cumulative: 0 1 3 5 6 6 6 6 7

Bu şu anlama gelir:

  • 1'e eşit veya ondan küçük 1 eleman vardır.

  • 2'ye eşit veya ondan küçük 3 eleman vardır.

  • 3'e eşit veya ondan küçük 5 eleman vardır.

  • 8'e eşit veya ondan küçük 7 eleman vardır.

Kümülatif sayım, algoritmanın çıktı dizisindeki her değerin doğru nihai konumunu bilmesine yardımcı olur.

Stabil Sayma Sıralaması İçin Manuel Çalıştırma

Aynı girişi kullanalım:

[4, 2, 2, 8, 3, 3, 1]

Frekans sayımı şudur:

Value:  0 1 2 3 4 5 6 7 8
Count:  0 1 2 2 1 0 0 0 1

Kümülatif sayım şudur:

Value:       0 1 2 3 4 5 6 7 8
Cumulative: 0 1 3 5 6 6 6 6 7

Şimdi girişle aynı boyutta bir çıktı dizisi oluşturuyoruz:

Output: [_, _, _, _, _, _, _]

Sıralamayı stabil tutmak için orijinal diziyi sağdan sola işliyoruz.

Son değer 1'dir. 1'in kümülatif sayımı 1'dir, bu yüzden 1, 0. dizine gider. Sonra 1'in sayımını azaltırız.

Output: [1, _, _, _, _, _, _]

Sağdan bir sonraki değer 3'tür. 3'ün kümülatif sayımı 5'tir, bu yüzden 3, 4. dizine gider. Sonra 3'ün sayımını azaltırız.

Output: [1, _, _, _, 3, _, _]

Bir sonraki değer tekrar 3'tür. 3'ün kümülatif sayımı şimdi 4'tür, bu yüzden bu 3, 3. dizine gider.

Output: [1, _, _, 3, 3, _, _]

Bir sonraki değer 8'dir. 8'in kümülatif sayımı 7'dir, bu yüzden 8, 6. dizine gider.

Output: [1, _, _, 3, 3, _, 8]

Bir sonraki değer 2'dir. 2'nin kümülatif sayımı 3'tür, bu yüzden 2, 2. dizine gider.

Output: [1, _, 2, 3, 3, _, 8]

Bir sonraki değer tekrar 2'dir. 2'nin kümülatif sayımı şimdi 2'dir, bu yüzden bu 2, 1. dizine gider.

Output: [1, 2, 2, 3, 3, _, 8]

Son değer 4'tür. 4'ün kümülatif sayımı 6'dır, bu yüzden 4, 5. dizine gider.

Output: [1, 2, 2, 3, 3, 4, 8]

Stabil Sayma Sıralaması sonucu şudur:

[1, 2, 2, 3, 3, 4, 8]

Düz sayılar için sonuç, basit versiyonla aynı görünür. Fark, eşit değerlerin daha büyük kayıtlara veya nesnelere ait olduğunda önem kazanır.

Stabil Sayma Sıralaması İçin Sözde Kod

stableCountingSort(array):
    max = find maximum value in array

    count = array of size max + 1 filled with 0
    output = array of same size as input

    for each value in array:
        count[value] = count[value] + 1

    for i from 1 to max:
        count[i] = count[i] + count[i - 1]

    for i from length(array) - 1 down to 0:
        value = array[i]
        position = count[value] - 1
        output[position] = value
        count[value] = count[value] - 1

    return output

Bu versiyon, girişi sağdan sola işlediği ve değerleri doğru bir şekilde yerleştirmek için kümülatif sayımları kullandığı için stabildir.

PHP'de Stabil Sayma Sıralaması

İşte stabil bir PHP uygulaması:

<?php

function stableCountingSort(array $numbers): array
{
    if ($numbers === []) {
        return [];
    }

    $max = max($numbers);
    $count = array_fill(0, $max + 1, 0);
    $output = array_fill(0, count($numbers), 0);

    foreach ($numbers as $number) {
        $count[$number]++;
    }

    for ($i = 1; $i <= $max; $i++) {
        $count[$i] += $count[$i - 1];
    }

    for ($i = count($numbers) - 1; $i >= 0; $i--) {
        $value = $numbers[$i];
        $position = $count[$value] - 1;

        $output[$position] = $value;
        $count[$value]--;
    }

    return $output;
}

$numbers = [4, 2, 2, 8, 3, 3, 1];

print_r(stableCountingSort($numbers));

Bu versiyon bir çıktı dizisi ve kümülatif sayımlar kullanır. Eşit elemanların sırası önemli olduğunda daha uygundur.

JavaScript'te Stabil Sayma Sıralaması

function stableCountingSort(numbers) {
    if (numbers.length === 0) {
        return [];
    }

    const max = Math.max(...numbers);
    const count = new Array(max + 1).fill(0);
    const output = new Array(numbers.length);

    for (const number of numbers) {
        count[number]++;
    }

    for (let i = 1; i <= max; i++) {
        count[i] += count[i - 1];
    }

    for (let i = numbers.length - 1; i >= 0; i--) {
        const value = numbers[i];
        const position = count[value] - 1;

        output[position] = value;
        count[value]--;
    }

    return output;
}

const numbers = [4, 2, 2, 8, 3, 3, 1];

console.log(stableCountingSort(numbers));

Çıktı şöyle olacaktır:

[1, 2, 2, 3, 3, 4, 8]

Bu uygulama, kümülatif sayımların nihai konumları nasıl kontrol ettiğini anlamak için faydalıdır.

Negatif Sayıları Yönetme

Temel Sayma Sıralaması uygulaması, tüm değerlerin negatif olmayan tamsayılar olduğunu varsayar. Bunun nedeni, dizi dizinlerinin genellikle 0'dan başlaması ve değeri dizin olarak kullanmamızdır.

Giriş negatif sayılar içeriyorsa, bir ofset kullanarak sorunu çözebiliriz.

Örneğin:

[-3, -1, 2, 0, -1]

Minimum değer -3'tür. Her değeri minimum değeri çıkararak kaydırabiliriz:

index = value - min

Yani:

  • -3, 0. dizin olur.

  • -1, 2. dizin olur.

  • 0, 3. dizin olur.

  • 2, 5. dizin olur.

Sıralanmış sonucu yeniden oluştururken, dizini orijinal değerine geri dönüştürüyoruz:

value = index + min

PHP'de Negatif Sayılarla Sayma Sıralaması

<?php

function countingSortWithNegativeNumbers(array $numbers): array
{
    if ($numbers === []) {
        return [];
    }

    $min = min($numbers);
    $max = max($numbers);
    $range = $max - $min + 1;

    $count = array_fill(0, $range, 0);

    foreach ($numbers as $number) {
        $count[$number - $min]++;
    }

    $sorted = [];

    for ($i = 0; $i < $range; $i++) {
        while ($count[$i] > 0) {
            $sorted[] = $i + $min;
            $count[$i]--;
        }
    }

    return $sorted;
}

$numbers = [-3, -1, 2, 0, -1];

print_r(countingSortWithNegativeNumbers($numbers));

Çıktı şöyle olacaktır:

Array
(
    [0] => -3
    [1] => -1
    [2] => -1
    [3] => 0
    [4] => 2
)

Bu ofset tekniği, Sayma Sıralamasını negatif tamsayılarla çalıştırırken aynı sayma fikrini korumasını sağlar.

Sayma Sıralamasının Zaman Karmaşıklığı

Zaman karmaşıklığı, bir algoritmanın çalışma süresinin giriş boyutu arttıkça nasıl büyüdüğünü açıklar. Sayma Sıralamasının, hem eleman sayısına hem de değer aralığına bağlı olduğu için karşılaştırma tabanlı algoritmalardan farklı bir zaman karmaşıklığı vardır.

Sayma Sıralamasının zaman karmaşıklığı şöyledir:

O(n + k)

Burada:

  • n giriş dizisindeki eleman sayısıdır.

  • k olası değerlerin aralığıdır.

Örneğin, 0 ile 100 arasındaki 1.000 sınav puanını sıralarsak, n 1.000 ve k 101 olur. Bu çok verimlidir.

Sayma Sıralaması Neden O(n + k)'dir

Sayma Sıralama birkaç doğrusal adım gerçekleştirir:

  1. Değerleri saymak için giriş dizisini tarar. Bu O(n) maliyetine sahiptir.

  2. Sayım dizisini tarar. Bu O(k) maliyetine sahiptir.

  3. Çıktı dizisini oluşturur. Bu, uygulamaya bağlı olarak O(n) veya O(n + k) maliyetine sahiptir.

Bu adımlar birleştirildiğinde, sonuç şöyledir:

O(n + k)

Bu, k küçük veya n'ye yakın olduğunda O(n log n)'den daha hızlıdır. Ancak k aşırı büyükse, Sayma Sıralama verimsiz hale gelebilir.

En İyi Durum Zaman Karmaşıklığı

Sayma Sıralamasının en iyi durum zaman karmaşıklığı şöyledir:

O(n + k)

Sayma Sıralama, giriş zaten sıralanmış olsa bile elemanları saymaya ve sayım dizisini işlemeye devam eder. Eklemeli Sıralamanın aksine, dizi zaten sıralandığı için O(n) olmaz.

Ortalama Durum Zaman Karmaşıklığı

Ortalama durum zaman karmaşıklığı da şöyledir:

O(n + k)

Algoritma, girişin orijinal sırasından bağımsız olarak aynı sayma ve yeniden yapılandırma adımlarını takip eder.

En Kötü Durum Zaman Karmaşıklığı

En kötü durum zaman karmaşıklığı şöyledir:

O(n + k)

Ancak, k çok büyük olduğunda pratik maliyet yüksek hale gelir. Örneğin, değerleri 0 ile 1.000.000 arasında değişen 10 sayıyı sıralamak, 1.000.001 konumlu bir sayım dizisi gerektirir.

Bu nedenle Sayma Sıralama, yalnızca değer aralığı makul olduğunda verimlidir.

Sayma Sıralamasının Alan Karmaşıklığı

Sayma Sıralaması, sayım dizisi için ek bellek gerektirir. Stabil Sayma Sıralaması ayrıca bir çıktı dizisi gerektirir.

Alan karmaşıklığı genellikle şöyledir:

O(n + k)

Burada n, giriş boyutu ve k, değer aralığıdır.

Sayım dizisi O(k) alan gerektirir ve çıktı dizisi stabil versiyonda O(n) alan gerektirir. Basit versiyon bazı uygulamalarda ayrı bir çıktı dizisinden kaçınabilir, ancak yine de sayım dizisine ihtiyaç duyar.

Sayma Sıralaması Stabil mi?

Sayma Sıralaması stabil olabilir, ancak her uygulama stabil değildir.

Değerleri yalnızca sayan ve sıralanmış diziyi yeniden oluşturan basit versiyon, düz sayılar için uygundur, ancak orijinal konumları takip etmediği için eşit kayıtların sırasını korumaz.

Stabil versiyon, kümülatif sayımlar kullanır ve girişi sağdan sola işler. Bu, eşit elemanların göreceli sırasını korur.

Dolayısıyla doğru cevap şudur:

  • Sayılar için basit Sayma Sıralaması: stabilite çok görünür değildir.

  • Kümülatif sayım ile stabil Sayma Sıralaması: stabildir.

  • Kayıtlar için kümülatif yerleştirme olmadan Sayma Sıralaması: mutlaka stabil değildir.

Sayma Sıralaması Yerinde mi? (In-Place)

Sayma Sıralaması genellikle yerinde bir sıralama algoritması olarak kabul edilmez çünkü sayım dizisi için ek bellek gerektirir. Stabil Sayma Sıralaması ayrıca bir çıktı dizisi gerektirir.

Bu, az miktarda ek bellek kullanarak sıralama yapabilen Eklemeli Sıralama veya yerinde Hızlı Sıralama gibi algoritmalardan farklıdır.

Sayma Sıralaması, hızı bellek karşılığında takas eder. Çok hızlı olabilir, ancak değer aralığına orantılı ek depolama alanına ihtiyaç duyar.

Sayma Sıralaması ile Karşılaştırma Tabanlı Sıralama

Karşılaştırma tabanlı algoritmalar elemanları karşılaştırarak sıralama yapar. Örnekler arasında Kabarcık Sıralaması, Seçmeli Sıralama, Eklemeli Sıralama, Birleştirmeli Sıralama, Yığın Sıralaması ve Hızlı Sıralama bulunur.

Sayma Sıralaması, elemanlar arasında doğrudan karşılaştırmalardan kaçınır. Bunun yerine, değerleri bir sayım dizisindeki dizinler olarak kullanır.

Bu fark önemlidir çünkü karşılaştırma tabanlı sıralama algoritmaları, genel sıralama için teorik olarak O(n log n) alt sınırına sahiptir. Sayma Sıralaması, değer aralığı hakkında bilgi kullandığı için belirli koşullar altında bundan daha hızlı olabilir.

Ancak, Sayma Sıralaması, karşılaştırma tabanlı sıralama için evrensel bir alternatif değildir. Yalnızca veriler tamsayı tabanlı olduğunda ve aralık çok büyük olmadığında iyi çalışır.

Sayma Sıralaması ile Hızlı Sıralama

Hızlı Sıralama (Quicksort), genel amaçlı, karşılaştırma tabanlı bir sıralama algoritmasıdır. Sayılar, dizeler, tarihler ve özel karşılaştırma kuralları olan nesneler gibi birçok karşılaştırılabilir veri türünü sıralayabilir.

Sayma Sıralaması daha özelleşmiştir. Sınırlı bir aralıktaki tamsayılar için en iyi şekilde çalışır.

  • Hızlı Sıralama ortalama zaman karmaşıklığı O(n log n)'dir.

  • Sayma Sıralaması zaman karmaşıklığı O(n + k)'dir.

  • Hızlı Sıralama genellikle yerindedir (in-place).

  • Sayma Sıralaması ek belleğe ihtiyaç duyar.

  • Hızlı Sıralama genel karşılaştırılabilir değerler için çalışır.

  • Sayma Sıralaması esas olarak tamsayı aralıkları için çalışır.

Eğer k küçükse, Sayma Sıralaması daha hızlı olabilir. Eğer k çok büyükse veya değerler tamsayı değilse, Hızlı Sıralama veya yerleşik sıralama fonksiyonları genellikle daha iyidir.

Sayma Sıralaması ile Radix Sıralaması

Sayma Sıralaması, Radix Sıralaması içinde genellikle bir alt program olarak kullanılır. Radix Sıralaması sayıları basamak basamak sıralar ve Sayma Sıralaması, her bir basamak konumunu stabil bir şekilde sıralamak için yaygın olarak kullanılır.

Stabil Sayma Sıralamasının önemli olmasının nedenlerinden biri budur. Eğer Sayma Sıralaması stabil olmasaydı, Radix Sıralaması birçok uygulamada doğru çalışmazdı.

Sayma Sıralaması, aralık yönetilebilir olduğunda tüm değere göre sıralama yapar. Radix Sıralaması ise büyük sayıları basamaklara veya karakterlere ayırır ve adım adım sıralar.

Geliştiriciler Sayma Sıralamasını Ne Zaman Kullanmalı?

Geliştiriciler, veriler algoritmanın güçlü yönleriyle eşleştiğinde Sayma Sıralamasını kullanmalıdır.

Sayma Sıralaması şu durumlarda kullanışlıdır:

  • Değerler tamsayıdır.

  • Değer aralığı küçük veya makuldür.

  • Eleman sayısı aralığa göre büyüktür.

  • Doğrusal zamanda sıralama isteniyor.

  • Veri birçok tekrarlayan değer içeriyor.

  • Stabil sıralama gerekiyor ve kümülatif sayım kullanılabilir.

Örneğin, 0'dan 100'e kadar binlerce öğrenci puanını sıralamak, Sayma Sıralaması için güçlü bir kullanım senaryosudur.

Sayma Sıralaması Ne Zaman Kullanılmamalıdır

Sayma Sıralaması, değer aralığı giriş boyutuna kıyasla çok büyük olduğunda kullanılmamalıdır.

Örneğin, bu giriş iyi bir kullanım senaryosu değildir:

[5, 900000, 42]

Dizi sadece üç değere sahip, ancak aralık çok büyük. 900000'e kadar bir sayım dizisi oluşturmak bellek israfına neden olur.

Sayma Sıralaması ayrıca şunlar için uygun değildir:

  • Dönüşüm yapılmadan kayan noktalı sayılar.

  • Tamsayı anahtarlara eşleştirilmemiş dizeler.

  • Sayısal anahtarı olmayan nesneler.

  • Büyük seyrek aralıklar.

  • Bellek kullanımının çok düşük olması gereken durumlar.

Bu durumlarda geliştiriciler genellikle yerleşik sıralama fonksiyonlarını veya Hızlı Sıralama, Birleştirmeli Sıralama veya TimSort gibi algoritmaları kullanmalıdır.

Pratik Örnek: Sınav Puanlarını Sıralama

Sayma Sıralaması, sınav puanlarını sıralamak için doğal bir uyum sağlar çünkü puanlar genellikle 0'dan 100'e kadar sınırlı bir aralığa sahiptir.

<?php

$scores = [85, 70, 100, 70, 90, 85, 60];

$sortedScores = countingSort($scores);

print_r($sortedScores);

Sonuç şöyle olacaktır:

Array
(
    [0] => 60
    [1] => 70
    [2] => 70
    [3] => 85
    [4] => 85
    [5] => 90
    [6] => 100
)

Bu verimlidir çünkü 0'dan 100'e kadar olan aralık küçük ve tahmin edilebilirdir.

Pratik Örnek: Ürün Derecelendirmelerini Sıralama

Bir başka iyi kullanım senaryosu, 1'den 5'e kadar ürün derecelendirmelerini sıralamaktır.

Ratings: [5, 3, 4, 5, 2, 1, 4, 3]

Olası değerler yalnızca 1, 2, 3, 4 ve 5'tir. Bu, sayım dizisi çok küçük olduğu için Sayma Sıralamasını çok verimli kılar.

Sorted ratings: [1, 2, 3, 3, 4, 4, 5, 5]

Olası değerlerin sayısı az olduğunda, Sayma Sıralaması hem basit hem de hızlı olabilir.

Sayma Sıralamasını Uygularken Yapılan Yaygın Hatalar

Yeni başlayanlar genellikle Sayma Sıralaması ile hata yaparlar çünkü dizi dizinlerini özel bir şekilde kullanır.

Yaygın hatalar şunlardır:

  • Sayma Sıralamasını doğrudan tamsayı olmayan değerlerle kullanmak.

  • Boş dizileri işlemeyi unutmak.

  • Maksimum değeri kontrol etmeden bir sayım dizisi oluşturmak.

  • Negatif sayıları göz ardı etmek.

  • Çok geniş bir değer aralığı için çok fazla bellek kullanmak.

  • Frekans sayısını kümülatif sayım ile karıştırmak.

  • Uygulama sırayı korumadığında algoritmayı stabil olarak adlandırmak.

En önemli pratik hata, k'nin çok büyük olduğu durumlarda Sayma Sıralamasını kullanmaktır. Bu durumda algoritma bellek israfına neden olabilir ve verimsiz hale gelebilir.

Sayma Sıralamasını Kullanmadan Önce Pratik Kontrol Listesi

Sayma Sıralamasını seçmeden önce geliştiriciler şu soruları sorabilirler:

  • Tüm değerler tamsayı mı?

  • Minimum değer nedir?

  • Maksimum değer nedir?

  • Aralık yeterince küçük mü?

  • Giriş Sayma Sıralamasından faydalanacak kadar büyük mü?

  • Stabil sıralamaya ihtiyacım var mı?

  • Sayım dizisi kabul edilebilir bellek kullanacak mı?

  • Yerleşik bir sıralama daha basit ve güvenli olur muydu?

Eğer aralık küçükse ve değerler tamsayı tabanlıysa, Sayma Sıralaması mükemmel bir seçim olabilir. Değilse, başka bir sıralama algoritması daha iyi olabilir.

Sayma Sıralamasının Avantajları

Sayma Sıralamasının doğru durumda kullanıldığında çeşitli avantajları vardır.

  • O(n + k) zamanda çalışabilir.

  • Eleman karşılaştırmalarına bağlı değildir.

  • Küçük tamsayı aralıkları için çok verimlidir.

  • Tekrarlayan değerleri iyi işler.

  • Kümülatif sayımlarla uygulandığında stabil olabilir.

  • Radix Sıralamasının bir parçası olarak kullanışlıdır.

Bu avantajlar, Sayma Sıralamasını hem algoritma eğitiminde hem de pratik özel sıralama problemlerinde önemli kılar.

Sayma Sıralamasının Dezavantajları

Sayma Sıralamasının ayrıca sınırlamaları vardır.

  • Büyük değer aralıkları için uygun değildir.

  • Ek bellek gerektirir.

  • Esas olarak tamsayılar için tasarlanmıştır.

  • Eşleme yapılmadan dizeleri, ondalık sayıları veya karmaşık nesneleri doğrudan sıralamaz.

  • Giriş seyrek olduğunda bellek israfına neden olabilir.

  • Evrensel bir genel amaçlı sıralama algoritması değildir.

Sayma Sıralaması güçlüdür, ancak yalnızca veriler varsayımlarına uyduğunda.

Sonuç

Sayma Sıralaması, her bir değerin kaç kez göründüğünü sayarak tamsayı değerlerini sıralayan, karşılaştırma tabanlı olmayan bir sıralama algoritmasıdır. Sayımları depolamak için bir frekans dizisi kullanır ve ardından sıralanmış diziyi bu sayımlardan yeniden oluşturur.

Algoritmanın zaman karmaşıklığı O(n + k)'dir; burada n, eleman sayısı ve k, olası değerlerin aralığıdır. Bu, k küçük veya n'ye yakın olduğunda Sayma Sıralamasını çok verimli kılar.

Stabil Sayma Sıralaması, eşit elemanların göreceli sırasını korumak için kümülatif sayımlar ve bir çıktı dizisi kullanır. Bu stabil versiyon, kayıtları sıralarken veya Sayma Sıralamasının Radix Sıralaması içinde kullanıldığında özellikle önemlidir.

Sayma Sıralaması, her sıralama problemi için en iyi seçim değildir. Ek bellek gerektirir ve sınırlı bir aralıktaki tamsayılarla en iyi şekilde çalışır. Ancak, sınav puanları, derecelendirmeler, küçük ID'ler ve tekrarlayan sayısal kategoriler gibi durumlarda basit, hızlı ve oldukça etkili olabilir.

Veri yapıları ve algoritmaları öğrenen geliştiriciler için Sayma Sıralaması önemli bir algoritmadır çünkü sıralama hakkında yeni bir düşünme biçimi sunar. Elemanları karşılaştırmak yerine, doğru koşullar altında verimli sıralama elde etmek için sayma, frekans dizileri, kümülatif konumlar ve aralık tabanlı mantık kullanır.