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:
- 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.
- Sıralanacak dizinin üzerinden geçerek bütün öğeleri ilgili güvercin yuvasına yerleştir.
- 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.
