Algoritmo di ordinamento
Da Wikipedia, l'enciclopedia libera.
Un algoritmo di ordinamento ((EN) sorting) è un algoritmo che viene utilizzato per elencare gli elementi di un insieme secondo una sequenza stabilita da una relazione d'ordine, in modo che ogni elemento sia minore (o maggiore) di quello che lo segue. In assenza di altre specifiche, la relazione d'ordine viene sempre considerata totale (cioè tale da rendere sempre possibile il confronto tra due elementi dell'assieme): le relazioni d'ordine parziale danno origine agli algoritmi di ordinamento topologico. A seconda del verso della relazione considerato, un ordinamento può essere ascendente o discendente.
Indice |
[modifica] Relazioni d'ordine e chiavi
La relazione d'ordine che intercorre tra gli elementi dell'insieme può essere:
- quella naturale (se esiste) per l'insieme preso in considerazione (ad esempio la relazione di <= per sottoinsiemi dei numeri naturali)
- una relazione definita dalle necessita' dell'applicazione.
É frequente il caso in cui l'algoritmo di ordinamento non opera direttamente sui dati di interesse, ma su un diverso insieme di dati che sono in collegamento biunivoco con quello dei dati di interesse: questo è detto l'insieme delle chiavi. Nel caso frequente in cui i dati sono costituiti da record, le chiavi sono spesso costituite dalla combinazione di uno o più campi del record stesso (questo avviene regolarmente nei database relazionali). L'obiettivo dei metodi di ordinamento consiste nel riorganizzare i record in modo tale che le loro chiavi siano disposte secondo un ordine ben definito (di norma in ordine numerico o alfabetico). Le specifiche caratteristiche delle chiavi e dei record possono variare notevolmente da un'applicazione all'altra. La nozione astratta di ordinamento prescinde da tali caratteristiche.
[modifica] Complessità degli algoritmi di ordinamento
La ricerca e l'ottimizzazione di algoritmi di ordinamento è molto importante per alcuni ambiti informatici e per queste classi di algoritmi sono stati dimostrati svariati teoremi che ne definiscono i limiti. Il più importante è il seguente:
- Teorema: La complessità in tempo di un qualsiasi algoritmo di ordinamento per confronto è pari a Ω(NlogN), dove N è il numero di elementi da ordinare.
Questo teorema fissa il limite inferiore di complessità per gli algoritmi che si basano sul paragone di coppie di chiavi (per confronto). Nulla è noto su altri algoritmi di ordinamento, nemmeno quali possano essere. Sono stati ipotizzati (ma non prodotti) algoritmi di ordinamento totalmente quantistico, che potrebbero avere un più basso limite inferiore di complessità.
[modifica] Ordinamento interno e ordinamento esterno
Se il file da ordinare, o la struttura dati, può essere contenuto in memoria, il metodo viene detto interno=. L'ordinamento di file residenti su disco o su nastro viene chiamato ordinamento esterno: la differenza principale tra i due tipi di ordinamento sta nel fatto che mentre nel primo è possibile accedere direttamente a un record, nel secondo i record devono essere indirizzati in modo sequenziale o al più per grandi blocchi.
[modifica] Ordinamento adattivo
Solitamente un algoritmo di ordinamento sfrutta operazioni di confronto e scambio. Se tali operazioni vengono svolte in modo indipendente dai dati di input l'algoritmo viene definito non adattivo. Mentre se un metodo di ordinamento esegue diverse sequenze di operazioni in funzione del risultato dei confronti si ha un algoritmo adattivo.
[modifica] Stabilità di un algoritmo
Un metodo di ordinamento si dice stabile se preserva l'ordine relativo dei dati con chiavi uguali all'interno del file da ordinare. Ad esempio se si ordina per anno di corso una lista di studenti già odinata alfabeticamente un metodo stabile produce una lista in cui gli alunni dello stesso anno sono ancora in ordine alfabetico mentre un ordinamento instabile probabilmente produrrà una lista senza più alcuna traccia del precedente ordinamento.
La stabilità può essere forzata aggiungendo prima dell'ordinamento un piccolo indice a ciascuna chiave o allungando in qualche altro modo le chiavi sulle quali operare.
[modifica] Elenco degli algoritmi di ordinamento
Vi sono varie classi di algoritmi di ordinamento, i più noti ed utilizzati sono gli algoritmi di ordinamento per confronto.
Nella tabella seguente vengono riportati gli algoritmi di ordinamento per confronto, riportandone la memoria occupata e la complessità nel caso "Migliore", "Medio" e "Peggiore".
| Nome | Migliore | Medio | Peggiore | Memoria |
|---|---|---|---|---|
| Avl sort | — | — | — | — |
| Bubble sort | — | — | — | — |
| B sort | — | — | — | — |
| B-Tree sort | — | — | — | — |
| B-Tree sort | — | — | — | — |
| Bitonic sort | — | — | — | — |
| Btm sort | — | — | — | — |
| Bucket sort | — | — | — | — |
| Comb sort | — | — | — | — |
| Counting sort | — | — | — | — |
| Gnome sort | — | — | — | — |
| Heap sort | — | — | — | —
|
| Insertion sort | — | — | — | — |
| Intro sort | — | — | — | — |
| Jump sort | — | — | — | — |
| Merge sort | — | — | — | — |
| Ms sort | — | — | — | — |
| Oet sort | — | — | — | — |
| Partition sort | — | — | — | — |
| Plasel sort | — | — | — | —
|
| Quicksort | — | — | — | — |
| Radix sort | — | — | — | — |
| Ripple sort | — | — | — | — |
| Selection sort | — | — | — | — |
| Several unique sort | — | — | — | — |
| Shaker sort | — | — | — | — |
| Shear sort | — | — | — | —
|
| Simple sort | — | — | — | — |
| Shell sort | — | — | — | — |
| Smooth sort | — | — | — | — |
| Stupid sort | — | — | — | — |
| Trippel sort | — | — | — | — |
[modifica] Collegamenti esterni e bibliografia
- (EN) D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching.
- Una breve guida agli algoritmi di ordinamento e ricerca
- (EN) Spiegazione e analisi di nolti algoritmi
- (EN) Applet Java che mostra graficamente il funzionamento di alcuni algoritmi
- (EN) Applet Java che mostra l'ordinamento con 22 algoritmi diversi
