Pigeonhole sort

Pigeonhole sort

Klasa	Algoritam za sortiranje
Struktura podataka	Niz
Najgora performanca	$O(N+n)$, gde je N raspon vrednosti ključeva, a n veličina niza
Najgora prostorna kompleksnost	$O(N+n)$

Pigeonhole je algoritam za sortiranje koji je dobar za sortiranje nizova elemenata, gde je broj elemenata jednak n i broj mogućih vrednosti ključeva jednak N. N i n su otprilike jednaki. Algoritam ima složenost od O(n + N). Vrlo je sličan sortiranju s prebrojavanjem, ali se razlikuje jer “pomera” članove dva puta. Jednom u “kofu” nizova i onda drugi put na konačno odredište, dok counting sort pravi pomoćni niz i onda ga koristi da izračuna konačno odredište svakog člana I stavlja ga na to mesto.

Pigeonhole sort radi na sledeći način:

1. Pošto smo dobili niz vrednosti koje treba sortirati, pravimo pomoćni niz „golubljih rupa“ koje su inicijalno prazne, gde svaka rupa odgovara jednom ključu. 
2. Prolazeći kroz niz koji koji treba da se sortira, svaka vrednost se stavlja u rupu koja odgovara ključu, tako da svaka rupa sadrži listu vrednosti koje imaju taj ključ. 
3. Prolazi kroz pigeonhole niz po redu i stavlja elemente iz nepraznih rupa nazad u niz. 

Primer

Pretpostavimo da sortiramo ove vrednosti parova po prvom elementu:

• (5, "hello")
• (3, "pie")
• (8, "apple")
• (5, "king")

Za svaku vrednost koja je između 3 i 8 pravimo rupu, i onda u nju stavljamo odgovarajući element:

• 3: (3, "pie")
• 4:
• 5: (5, "hello"), (5, "king")
• 6:
• 7:
• 8: (8, "apple")

Onda prolazimo kroz niz rupa po redu i onda vraćamo elemente u prvobitni niz.

Razlika između pigeonhole sorta i counting sorta je ta što u counting sortu ne postoji lista elemenata u pomoćniom nizu nego samo broj elemenata.

• 3: 1
• 4: 0
• 5: 2
• 6: 0
• 7: 0
• 8: 1

Za nizove koji gde je N mnogo veće od n koristi se bucket sort i on se smtra generalizacijom koja je efektivnija što se tiče i vremenske i prostorne složenosti.