algoritmi di sort

bubblesort

Bubble sort, versione "base"Facile da implementare, efficiente per piccoli inputs e operante in-place il bubblesort agisce considerando coppie adiacenti di elementi, e scambiandole se non rispettano la relazione d'ordine desiderata.
Se in una scansione del vettore non si effettuano scambi, significa che il vettore è ordinato.
Si chiama ordinamento a bolla perché dopo la prima scansione del vettore, l'elemento massimo si porta in ultima posizione (gli elementi più piccoli salgono come "bolle" verso le posizioni iniziali del vettore).

quicksort

Benchè l'algoritmo shell sort sia significativamente migliore dell' insertion sort, c'è ancora spazio per il miglioramento. Uno dei più popolari algoritmi di ordinamento è il quicksort che ha complessità O(nlogn) in media e O(n2) nel caso pessimo. Con le giuste precauzioni il caso pessimo si può evitare. Quicksort è di tipo non-stable e non è di tipo in-place siccome occorre uno spazio di stack.
Il quicksort lavora partizionando l'array che deve essere ordinato e ricorsivamente ordina ogni parte (l'algoritmo è ricorsivo nel senso che si richiama su ciascun sotto-vettore fino a quando non si ottengono sotto-vettori di lunghezza 1: a questo punto il vettore di partenza risulta ordinato) . In Partition (figura sotto), un elemento dell'array è selezionato come valore pivot. I valori più piccoli del pivot sono sistemati a sinistra del pivot, mentre i più grandi a destra.
Come il processo avanza, può essere necessario muovere il pivot in modo che l'ordine corretto rimanga. In questa maniera quicksort segue nell'ordinare l'array. Se siamo fortunati il pivot selezionato sarà la media di tutti i valori, dividendo in maniera equa l'array. Se è questo il caso l'array è diviso ad ogni passo a metà, e Partition deve esaminare tutti e n gli elementi: la complessità sarà O(nlogn). Per trovare un valore pivot, Partition potrebbe semplicemente selezionare il primo elemento (A[Lb]). Tutti gli altri valori dovrebbero essere comparati al valore pivot, e messi o a dx o a sx del pivot. Comunque, c'è un caso che fallisce miseramente. Si supponga che l'array è all'inizio in ordine. Partition selezionerà sempre il valore più basso come pivot e dividerà l'array con un elemento nella parte sx, e Ub-Lb elementi nell'altra. Ogni chiamata ricorsiva a quicksort diminuirà la grandezza dell'array. Perciò n chiamate ricorsive sranno richieste per fare l'ordinamento, risultando di complessità O(n2). Una soluzione a questo problema è selezionare casualmente un elemento come pivot. Questo renderebbe estremamente sfortunata l'occorrenza del caso pessimo.

tratto da wikipedia.org