18 Nisan 2014

Pigeonhole Sort (Güvercin Yuvası Sıralama) Algoritması

ibasoglu Algoritmalar, Sıralama Algoritmaları 0 Comments

Selamün Aleyküm Arkadaşlar;

Güvercin yuvası algoritması minimum ve maksimum sayılar arasındaki veriler için bir dizi oluşturup bu dizide sayıları sayıp, buna göre sıralama işlemi yapar. Pek kullanılmaz. Bunun sebebi sıralamanın hızlı şekilde nadiren oluşmasıdır.

Örnekle açıklayacak olursak eğer, şöyle bir dizimiz olsun.

Bu dizimizde 9 ve 19 arasında sayılar var. Arasındaki sayılar kadar güvercin yuvası oluşturuyoruz.

Sıfırıncı index dizideki minimum değeri, sonuncu index ise maksimum değeri temsil eder.

Şimdi A dizimizdeki sayılardan kaç tane varsa B dizimizde (+1 arttıralım) saydıralım.

 

Şimdi ise B dizisine baştan itibaren bakılır. hangi eleman 0’dan büyük ise o eleman sırasıyla diziye eklenir. Değeri -1 azaltılır. 0 olana kadar diziye eklenir. Sonra diğer elemanlara bakılır. Sonunda dizimiz sıralanmış olur.

 

void Main()
{
    int[] d = Pigeonhole_Sort(new int[] { 12, 16, 19, 10, 9});

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

    Console.ReadKey();
}

int[] Pigeonhole_Sort(int[] Dizi)
{
    //Min ve max değerleri bul
    int min = Dizi[0], max = Dizi[0];
    foreach (int x in Dizi){
        min = Math.Min(x, min);
        max = Math.Max(x, max);
    }

    //Yuvaları tanımla
    int[] yuvalar = new int[max - min + 1];

    //Sayıları say
    foreach (int x in Dizi)
        yuvalar[x - min]++;

    //Diziyi Sırala
    int k = 0;
    for (int i = 0; i < yuvalar.Length; i++)
        while (yuvalar[i]-- > 0)
            Dizi[k++] = i + min;

    return Dizi;
}

Proje dosyasını buradan indirebilirsiniz.

 

PHP

$d = Pigeonhole_Sort(array(12, 16, 19, 10, 9));

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

function Pigeonhole_Sort($Dizi)
{
    //Min ve max değerleri bul
    $min = $Dizi[0]; $max = $Dizi[0];
    foreach ($Dizi as $x){
        $min = min($x, $min);
        $max = max($x, $max);
    }

    //Yuvaları tanımla ve sıfırla
    $yuvalar = array();
    for ($i=0; $i < count(max - min + 1); $i++) { 
    	$yuvalar[$i] = 0;
    }

    //Sayıları say
    foreach ($Dizi as $x)
        $yuvalar[$x - $min]++;

    //Diziyi Sırala
    $k = 0;
    for ($i = 0; $i < count($yuvalar); $i++)
        while ($yuvalar[$i]-- > 0)
            $Dizi[$k++] = $i + $min;

    return $Dizi;
}

 

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.