Pigeonhole sort
Pigeonhole sort | |
---|---|
Classe | Algoritmo di ordinamento |
Struttura dati | Array |
Caso peggiore temporalmente | , dove è l'intervallo di valori chiave e è il numero di elementi |
Caso peggiore spazialmente | |
Manuale |
Il Pigeonhole sort è un algoritmo di ordinamento particolarmente adatto quando il numero di elementi () e la lunghezza dell'intervallo dei possibili valori chiave () 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:
- 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.
- 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.
- 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 è molto maggiore di , 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
Note
- ^ NIST's Dictionary of Algorithms and Data Structures: pigeonhole sort
- ^ Paul E. Black, Dictionary of Algorithms and Data Structures, su NIST. URL consultato il 6 novembre 2015.
Voci correlate
- Principio dei cassetti
- Radix sort
- Bucket sort
V · D · M | ||
---|---|---|
Teoria | Teoria della complessità computazionale · Notazione O Grande · Array · Lista · Stack · Coda · Ordinamento comparativo · Ordinamento adattivo | |
Algoritmi a scambio | Bubble sort · Shaker sort · Odd-even sort · Comb sort · Gnome sort · Quicksort | |
Algoritmi di selezione | Selection sort · Heap sort · Smoothsort | |
Algoritmi ad inserimento | Insertion sort · Shell sort · Tree sort · Library sort · Patience sorting | |
Algoritmi a fusione | Merge sort · Timsort | |
Algoritmi non comparativi | Radix sort · Bucket sort · Counting sort · Pigeonhole sort | |
Altri algoritmi | Rete di ordinamento · Ordinamento topologico · Ordinamento bitonico · Ordinamento delle frittelle | |
Algoritmi inefficienti | Stupid sort · Trippel sort |