18 Nisan 2014

Radix Sort (Taban veya Basamağa Göre Sıralama) Algoritması

ibasoglu Algoritmalar, Sıralama Algoritmaları 0 Comments

Selamün Aleyküm Arkadaşlar;

Radix sıralama algoritması ilk önce birler basamağındaki rakamı veya harfi karşılaştırıp bir sıralama yapar. Sonra o sıralamanın onlar basamağına göre tekrar dizilimini yapar. En fazla hangi basamaklı sayı varsa o basamağa kadar bu şekilde sıralama devam eder. Son basamak sıralamasında dizi sıralanmış olur.

Şöyle bir dizimiz olsun. Küçükten büyüğe doğru sıralayalım.

 

İlk önce birler basamağına göre sıralama yapılır.

 

Sonra onlar basamağına göre sıralama yapılır.

 

Sonra yüzler basamağına göre sıralama yapılır.

 

Son olarak en büyük sayı binler basamağında olduğu için binler basamağına göre sıralama yapılır.

 

Ve sonunda dizi sıralanmış olur.

Aslında her basamakta rakamlar arsındaki uzaklığa bakılır ve sıralama yapılır. Yani aslında basamaklar arasındaki rakamlara göre sayarak sıralama yapılır. Couting Sort (buradan bakabilirsiniz) sıralamasını kullanarak yazabiliriz. Sayı yerine rakamları sayacağımız için 0-9 uzunluğunda bir diziye ihtiyacımız var. Sayıları sayıp uzaklığına göre dizimize yerleştiririz. Tabiki bu son basamağa kadar tekrar edecektir. Dilerseniz while döngüsüyle veya recursive bir fonksiyonla yazabilirsiniz.

void Main()
{
int[] d = Radix_Sort(new int[]{1000, 32, 353, 21, 421});

//Konsola yaz
for (int i = 0; i < d.Length; i++){
    Console.Write(d[i] + " ");
}

Console.ReadKey();

}

int[] Radix_Sort(int[] dizi, int b = 1) {
    int[] a = new int[10];
    int[] c = new int[dizi.Length];

    int i = 0, ra = 0, p =  b * 10, k = 0;

    //Rakamlara göre say
    for (i = 0; i < dizi.Length; i++){
        ra = (dizi[i] % p) / b;

        //Kaçıncı basamağındaysa en büyük sayıyı al
        if(dizi[i] / p > k)
            k = dizi[i] / p;
        a[ra]++;
    }

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

    //a daki indexlere göre sayıları sırala
    for (i = dizi.Length -1; i >= 0; i--){
        ra = (dizi[i] % p) / b;
        c[--a[ra]] = dizi[i];
    }

    //Sayı sıfırdan büyükse 
    if(k > 0)
        return Radix_Sort(c, p);
    return c;
}

Proje dosyasını buradan indirebilirsiniz.

 

PHP

$d = Radix_Sort(array(56, 1002, 24, 1, 256));

for ($i=0; $i < count($d); $i++) { 
	echo $d[$i] . ' ';
}

function Radix_Sort($dizi, $b = 1) {
    $a = array();
    $c = array();

    $i = 0; $ra = 0; $p =  $b * 10; $k = 0;

    //a dizisini 0'la
    for ($i=0; $i < 10; $i++) { 
    	$a[$i] = 0;
    }

    //Rakamlara göre say
    for ($i = 0; $i < count($dizi); $i++){
        $ra = intval(($dizi[$i] % $p) / $b);

        //Kaçıncı basamağındaysa en büyük sayıyı al
        if(intval($dizi[$i] / $p) > $k)
            $k = intval($dizi[$i] / $p);
        $a[$ra]++;
    }

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

    //a daki indexlere göre sayıları sırala
    for ($i = count($dizi) - 1; $i >= 0; $i--){
        $ra = intval(($dizi[$i] % $p) / $b);
        $c[--$a[$ra]] = $dizi[$i];

    }

    //Sayı sıfırdan büyükse 
    if($k > 0)
        return Radix_Sort($c, $p);
    return $c;
}

 

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.