30 Nisan 2017 Pazar
Twitter

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

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.
İ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;
    }
}

Değerlendirme

Yazım dilinin sadeliği ve anlaşılabilirliği Puan: 0,65 (1 oy)
Yazıdaki kodların kalitesi Puan: 3,75 (1 oy)
İhtiyaca cevap verme Puan: 2,15 (1 oy)
Tavsiye edilebilirlik Puan: 0,75 (1 oy)
Genel değerlendirme Puan: 0,45 (1 oy)
Puanlamalar 5 üzerindendir.
  • Site Yorumları
  • Facebook Yorumları Facebook Yorumları
Yeni yorum yaz
Henüz bir yorum yazılmadı. İlk yazan siz olabilirsiniz.