Güvercin yuvası sıralaması

Vikipedi, özgür ansiklopedi

Güvercin yuvası sıralaması, n adet öğeyi N adet "güvercin yuvası" (sıralanacak öğelerin alabileceği olası değerlerin sayısı) ile (Θ(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.

The hidden constant for this algorithm depends critically on the density of the elements in the pigeonhole array. If there are many more array elements than items to be sorted, steps 1 and 3 will be relatively slow.

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.

[değiştir] Sözde kodu

N adet ayrık elemanı sıralayan güvercin yuvası sıralamasının sözde kodu aşağıdaki gibidir:

function pigeonhole_sort(array a[n])
    array b[N]
    var i,j
    
    zero_var (b)      (* zero out array b *)
    
    for i in [0...length(a)-1]
        b[a[i]] := b[a[i]]+1

    (* copy the results back to a *)
    j := 0
    for i in [0...length(b)-1]
        repeat b[i] times
            a[j] := i
            j := j+1