Qui il Titolo

L'efficienza della semplicità

Ho sempre pensato che le cose semplici siano sempre le migliori, oggi ne ho avuto la conferma.

Oggi ho studiato il countingSort, un algoritmo di ordinamento non sul posto e (volendo) stabile.

Questo algoritmo ha il pregio di avere una complessità O(n), diversamente da tutti gli algoritmi che ho visto finora (mergesort, insertionsort, quicksort...) che hanno come lowerbound Omega(n lgn).

Questo algoritmo ha bisogno solo di una piccola informazione in più, bisogna sapere l'intervallo in cui cadono gli elementi da ordinare, riesce ad abbattere il lowerbound nlgn in quanto non usa confronti fra gli elementi. Viaggia "fuori dagli schemi".

In parole povere questo algoritmo assegna ad ogni elemento della sequenza in input A una posizione finale e la conserva in un array C di supporto, alla fine mediante un semplice for si assegnano a B (l'array finale) gli elementi di A posizionati secondo quanto dice C.


Pseudocodice
(originale del Cormen)
consta di 4 cicli:(supponiamo di avere una sequenza A (lunga n) da ordinare che contiene valori appartenenti a [0, k])

1)inizializza l'array C a 0(superfluo a mio modo di vedere, dipende dal linguaggio di programmazione utilizzato)
2)Calcola le occorrenze di ogni x appartenente a [0,k] scorrendo A, C[x] contiene le occorrenze di x
3)Accumula i valori di C in modo da ottenere che C[x] contenga il numero di elementi minori di x.
4)Assegna a B i valori di A ordinati secondo quanto dice C.


Migliorie

1)Si potrebbe eliminare il primo ciclo se si conosce bene il linguaggio di programmazione che si usa (in C, come in Java, ad esempio è superfluo questo lavoro)
2)Aggiungendo un ciclo lineare (che quindi non modifica la complessità) si può evitare di chiedere, a chi vuole usare questo algoritmo, di fornire l'intervallo dei numeri da ordinare (calcolando max e min).


Difetti
Se k risulta essere molto più grande di n allora questo algoritmo è sconveniente.
Matematicamente:
n+k<nlgn <=> k<nlgn-n<=> k<n(lgn-1)

Per chi volesse approfondire.

Un saluto
Dario