Couting Sort (Saymalı Sıralama) Algoritması

, 2 Comments

Selamün Aleyküm Arkadaşlar;

Saymalı sıralama algoritması verilerin aralığını kullanarak sıralama yapar. Saymalı sıralama algoritması Harold H. Seward tarafından 1954 yılında yazılmıştır.

Elimizde şu şekilde bir A dizisi olsun:

SnapCrab_No-0032

 

İlk önce dizideki en büyük değer bulunur.  Dizideki en büyük değer 7’dir. 7 + 1 uzunluğunda bir başka dizi tanımlanır. Biz bunu B dizisi olarak tanımlayalım. Sonra B dizisinin tüm değerleri 0 yapılır.

SnapCrab_No-0033

 

Sonra A dizisiyle aynı uzunlukta başka bir dizi tanımlanır. Biz bunu C dizisi olarak tanımlayalım.

SnapCrab_No-0034

 

Sonra A dizisi birinci elemanından itibaren seçilir. Birinci elemanın değeri B dizinde index numarasını gösterir. B dizisindeki veri +1 arttırılır.

SnapCrab_No-0035

 

Sonra B dizisine n = n + (n-1) uygulanır. Yani bir elemanın değeri bir önceki elemanın değeriyle toplanır ve elemana yazılır.

SnapCrab_No-0036

A dizisinin sondan itibaren elemanı seçilir. Değeri B dizisinin indeksini verir. B elemanının değerinin bir eksiği,  C dizisindeki indeksi verir. C dizisindeki (B elemanının değeri – 1) indeksine, seçilen elemanın değeri yazılır. B elemanının değeri 1 azaltılır.

SnapCrab_No-0037

 

Böylelikle A dizisindeki elemanlar, C dizisinde sıralanmış olur.

C# Kod yapısı da aşağıdaki gibidir.

int[] a = new int[]{7, 3, 5, 1};

//En büyük değerin indeksini al
int enb = 0;
for (int i = 1; i < a.Length; i++)
{
    if (a[i] > a[enb])
        enb = i;
}

//B ve C dizilerini tanımla
int[] b = new int[a[enb] + 1];
int[] c = new int[a.Length];

//dizideki elemanları say
for (int i = 0; i < a.Length; i++)
{
    b[a[i]] += 1;
}

//n = n + (n - 1)
for (int i = 1; i < b.Length; i++)
{
    b[i] += b[i - 1];
}

//C dizisine sırala
for (int i = a.Length - 1; i >= 0; i--)
{
    c[b[a[i]]-- - 1] = a[i];
}

Proje dosyasını buradan indirebilirsiniz.

 

Hayırlı günler, sağlıcakla kalın.

Bu döküman www.ibasoglu.com’a aittir. Kaynak belirtmek suretiyle alıntı yapılabilir.