Qui troverete una breve descrizione dei principali algoritmi di ordinamento.
Da qui è possibile scaricare un programma dimostrativo
che permette di confrontare la velocitá di questi algoritmi.
NOTA: il programma è scritto in Visual-Basic, per cui servono i runtime di VB6
Consideriamo l'array diviso in due parti, la prima con solo il primo elemento, la seconda con tutti gli altri. Ad ogni iterazione prendiamo il primo elemento della seconda parte e lo inseriamo nella prima parte nella posizione giusta.
Nell'algoritmo precedente l'inserimento viene effettuato cercando la posizione in cui inserire l'elemento e spostando in avanti quelli posti successivamente. La ricerca viene effettuata nella prima parte che è già ordinata, quindi si può utilizzare la ricerca binaria per migliorare le prestazioni.
Cerchiamo nell'array il minimo. Scambiamolo di posizione col primo elemento. Quindi a partire dal secondo elemento facciamo una nuova ricerca, il minimo lo mettiamo in seconda posizione. Continuiamo così fino alla fine dell'array.
Eseguiamo una scansione dal fondo dell'array in cui confrontiamo e scambiamo le coppie di elementi adiacenti. Gli elementi vengono spostati verso l'alto o il basso come se fossero delle bollicine a seconda del loro peso. Al termine avremo il minimo che si trova in prima posizione. Per ordinare l'array basta fare n scansioni.
L'array può risultare ordinato anche prima di finire le n scansioni. Per cui si può tenere conto se nelle scansioni ci sono stati degli scambi, se no l'algoritmo termina. Si può ricordare, oltre che se ci sono stati scambi, anche la posizione dell'ultimo scambio. Gli elementi prima di tale posizione sono già ordinati, quindi le successive scansioni si possono fermare a questo indice.
Anche questo è un miglioramento di BubbleSort. BubbleSort presenta un'asimmetria, un elemento piccolo in fondo al vettore viene portato in cima con una sola scansione. Viceversa un elemento grande in cima al vettore viene spostato verso il basso di una sola posizione per passata. Per rimediare ShakerSort esegue le passate alternativamente dal basso all'alto e dall'alto al basso.
Questo è un perfezionamento di InsertionSort proposto da D. L. Shell. Prendiamo gli elementi distanziati di A posizioni e ordiniamoli separatamente dal resto utilizzando InsertionSort. Ripetiamo prendendo gli elementi distanziati di B posizioni. Nelle varie iterazioni sarà A > B > C .., e l'ultimo valore sarà 1. Non esistono metodi precisi per determinare i valori da usare per A, B, C, ... . Nel test ho scelto 9, 5, 3, 1.
Questo è un perfezionamento di SelectionSort proposto da J. Williams. In SelectionSort si fanno delle continue ricerche dell'elemento minimo. Tali ricerche possono essere velocizzate se costruiamo un albero che faccia da indice. Se utilizziamo un albero binario possiamo rappresentarlo efficientemente con la struttura detta heap, in cui in sostanza abbiamo un vettore che nelle posizioni 2h e 2h+1 contiene i figli sinistro e destro del nodo h.
Questo è un perfezionamento di BubbleSort proposto da C. A. R. Hoare. BubbleSort esegue scambi tra elementi adiacenti. QuickSort invece li effettua su distanze lunghe. Si sceglie un elemento x dell'array, quindi si scansionano le due parti in cui viene separato, ogni volta che in una parte si trova un elemento maggiore di x e nell'altro uno minore, si scambiano. Al termine in un parte ci saranno i valori < x, nell'altra quelli > x. Per ognuna delle due parti, si chiama ricorsivamente QuickSort.
QuickSort è un programma ricorsivo. Come ogni programma ricorsivo può essere trasformato in iterativo gestendo manualmente la pila dei parametri.
Nel QuickSort viene sempre processata prima la partizione di sinistra. Si può ottenere un miglioramento processando per prima la partizione più piccola.
Dividiamo l'array in due parti, ordiniamo ciascuna chiamando ricorsivamente MergeSort, quindi facciamo il Merge dei due vettori.
Indichiamo con N i record presenti nel file, con M i record che è possibile caricare in memoria.
Se M >= N, carichiamo il file in memoria, ordiniamo e riscriviamo. Se M < N, dividiamo il file in blocchi di M elementi, ordiniamo ogni blocco indipendentemente, salvando il risultato in un file diverso, quindi fondiamo i vari file in uno unico. Se N > M^2 il numero di blocchi che si formano è > M, quindi la fusione dovrà essere effettuata in più passi.
Questo sistema è inefficiente, ma può essere migliorato organizzando la memoria in frame contenenti più blocchi ciascuno.