Sıralama Algoritmaları - 8. Güvercin Yuvası Sıralaması (Pigeonhole Sort)

İngilizce Adı	Pigeonhole Sort
Ortalama	O(n+2k)
En kötü	O(n+2k)
Bellek	O(2k)
Kararlı mı?	Evet
Yöntem	Karşılaştırmadan Sıralayan

Güvercin yuvası sıralaması, n adet öğeyi N adet "güvercin yuvası" (sıralanacak öğelerin alabileceği olası değerlerin sayısı) ile (O(n + N)) karmaşıklığıyla sıralayan bir sıralama algoritmasıdır. N O(n) olduğunda algoritma doğrusal zamanda çalışır. Bir sıralama algoritmasının dizideki öğeleri sıralamak için her bir öğeye en az bir kere bakması zorunlu olduğundan doğrusal zaman sıralama algoritmasından bağımsız olarak erişilebilecek en iyi sonuçtur.

Güvercin yuvası algoritması aşağıdaki biçimde çalışır:

1. Başlangıçta boş "güvercin yuvalarının" bulunduğu her bir arama anahtarı aralığına bir güvercin yuvası düşecek biçimde bir dizi oluştur.
2. Sıralanacak dizinin üzerinden geçerek bütün öğeleri ilgili güvercin yuvasına yerleştir.
3. Güvercin yuvası disizinin üzerinden sırayla gerçerek boş olmayan bütün yuvalardaki öğeleri asıl diziye aktar.

Güvercin yuvası sıralaması hızlı çalışması için gereken durumların nadiren oluşması ve diğer daha esnek ve neredeyse aynı hızda çalışan algoritmaların kullanımı daha kolay olduğu için pek kullanılmaz. Özellikle kova sıralaması güvercin yuvası sıralamasının uygulamada daha fazla kullanılan bir türüdür.

Kod örneği:

public class GuvercinYuvasiSiralama
{
	int[] dizi;
	public int[] Dizi
    {
        get { return dizi; }
        set { dizi = (int[])value.Clone(); }
    }
    public GuvercinYuvasiSiralama()
    {
        //
        // TODO: Add constructor logic here
        //
    }

    public void Sirala()
    {
        PigeonholeSort();
    }

    public override string ToString()
    {
        return "Güvercin Yuvasi Sıralaması";
    }

    void PigeonholeSort()
    {
        // size of range of values in the list (ie, number of pigeonholes we need)
        int min = Dizi[0], max = Dizi[0];
        foreach (int x in Dizi)
        {
            min = Math.Min(x, min);
            max = Math.Max(x, max);
        }
        int size = max - min + 1;

        // our array of pigeonholes
        int[] holes = new int[size];

        // Populate the pigeonholes.
        foreach (int x in Dizi)
            holes[x - min]++;

        // Put the elements back into the array in order.
        int i = 0;
        for (int count = 0; count < size; count++)
            while (holes[count]-- > 0)
                Dizi[i++] = count + min;
    }
}

---

#sıralama-algoritmaları #sorthing-algorithms #güvercin-yuvası-sıralaması #pigeonhole-sort