Pigeonhole sort

Pigeonhole sort
Classe	Algoritmo di ordinamento
Struttura dati	Array
Caso peggiore temporalmente	${\displaystyle O(N+n)}$, dove ${\displaystyle N}$ è l'intervallo di valori chiave e ${\displaystyle n}$ è il numero di elementi
Caso peggiore spazialmente	${\displaystyle O(N+n)}$
Manuale

Il Pigeonhole sort è un algoritmo di ordinamento particolarmente adatto quando il numero di elementi (${\displaystyle n}$) e la lunghezza dell'intervallo dei possibili valori chiave (${\displaystyle N}$) sono approssimativamente uguali.^[1] L'algoritmo ha una complessità temporale e spaziale di O(n + N). È simile al counting sort, ma differisce da quest'ultimo perché il pigeonhole muove gli elementi due volte: una volta nell'array di appoggio e poi di nuovo nella destinazione finale. ^[2] Il nome pigeonhole (tradotto in "buco della piccionaia") deriva dal nome inglese del principio dei cassetti, che ricorda il processo di assegnamento ad una cella all'interno dell'algoritmo.

L'algoritmo funziona come segue:

1. Dato un array di valori da ordinare, si alloca un array composto inizialmente di celle vuote (i "pigeonhole"), ciascuna per ogni valore compreso nel range dell'array iniziale.
2. Scorrendo l'array iniziale, si inserisce ogni valore nella cella corrispondente, in modo che ogni casella alla fine contenga una lista di tutti i valori che corrispondono alla stessa chiave.
3. Iterando in ordine sull'array di appoggio, si spostano gli elementi nelle celle non vuota nell'array originale.