Пигеонхоле сорт

Пигеонхоле је алгоритам за сортирање који је добар за сортирање низова елемената, где је број елемената једнак н и број могућих вредности кључева једнак Н. Н и н су отприлике једнаки. Алгоритам има сложеност од О(н + Н). Врло је сличан сортирању с пребројавањем, али се разликује јер “помера” чланове два пута. Једном у “кофу” низова и онда други пут на коначно одредиште, док цоунтинг сорт прави помоћни низ и онда га користи да израчуна коначно одредиште сваког члана I ставља га на то место.

Пигеонхоле сорт

Класа	Алгоритам за сортирање
Структура података	Низ
Најгора перформанца	$O(N+n)$, где је Н распон вредности кључева, а н величина низа
Најгора просторна комплексност	$O(N+n)$

Пигеонхоле сорт ради на следећи начин:

1. Пошто смо добили низ вредности које треба сортирати, правимо помоћни низ „голубљих рупа“ које су иницијално празне, где свака рупа одговара једном кључу. 
2. Пролазећи кроз низ који који треба да се сортира, свака вредност се ставља у рупу која одговара кључу, тако да свака рупа садржи листу вредности које имају тај кључ. 
3. Пролази кроз пигеонхоле низ по реду и ставља елементе из непразних рупа назад у низ. 

Пример

Претпоставимо да сортирамо ове вредности парова по првом елементу:

• (5, "хелло")
• (3, "пие")
• (8, "аппле")
• (5, "кинг")

За сваку вредност која је између 3 и 8 правимо рупу, и онда у њу стављамо одговарајући елемент:

• 3: (3, "пие")
• 4:
• 5: (5, "хелло"), (5, "кинг")
• 6:
• 7:
• 8: (8, "аппле")

Онда пролазимо кроз низ рупа по реду и онда враћамо елементе у првобитни низ.

Разлика између пигеонхоле сорта и цоунтинг сорта је та што у цоунтинг сорту не постоји листа елемената у помоћниом низу него само број елемената.

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

За низове који где је Н много веће од н користи се буцкет сорт и он се смтра генерализацијом која је ефективнија што се тиче и временске и просторне сложености.