Pigeonhole sort

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

Il Pigeonhole sort è un algoritmo di ordinamento particolarmente adatto quando il numero di elementi ($n$) e la lunghezza dell'intervallo dei possibili valori chiave ($N$) sono approssimativamente uguali. 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. 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.

Esempio

Si supponga di voler ordinare questa coppia di valori in base al loro primo elemento:

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

Per ogni valore tra 3 e 8 si alloca un "pigeonhole", e successivamente si sposta ogni elemento dell'array nella sua cella corrispondente:

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

Si scorre ora l'array di pigeonhole in ordine, e si riportano gli elementi nell'array iniziale.

La differenza fra il pigeonhole sort e il counting sort è che in quest'ultimo, l'array di appoggio non contiene le liste degli elementi forniti in input, ma solamente i relativi conteggi:

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

Usando questa informazione, si può eseguire una serie di scambi nell'array in modo tale da ordinarlo, muovendo gli elementi soltanto una volta.

Per array in cui $N$ è molto maggiore di $n$, il bucket sort è una generalizzazione che è molto più efficiente sia come tempo che come spazio.

Implementazione in Python

def pigeonhole_sort(a):
    min_  = min(a)
    size  = max(a) - min_ + 1
    holes = [[] for _ in range(size)]

    for x in a:
        holes[x - min_].append(x)

    i = 0
    for hole in holes:
        for x in hole:
            a[i] = x
            i += 1

Voci correlate

• Principio dei cassetti
• Radix sort
• Bucket sort