Elenco degli algoritmi di ordinamento
La seguente tabella riepiloga gli algoritmi di ordinamento.
La spiegazione del funzionamento è solo un promemoria, non ha intento di essere esauriente.
| Algoritmo | Complessità | Funzionamento |
|---|---|---|
| InsertionSort | O(n2) | (base) Si lascia il primo elemento dov'è
(passo induttivo) Per ogni elemento n, si trova il primo elemento maggiore tra quelli già ordinati, si sposta di una posizione da lì a n e si inserisce n tra quello appena minore e quello appena maggiore |
| SelectionSort | O(n2) | (base) Si scorre l'elenco trovando quello più piccolo e si scambia con il primo.
(passo induttivo) Posto che fino all'elemento n-1 l'elenco è ordinato e contiene solo elementi più piccoli di quelli ancora da ordinare, si scorre l'elenco da n alla fine e si scambiano l'n-esimo con il più piccolo. |
| BubbleSort | O(n2) | (base) Si confrontano il primo e il secondo elemento. Se il primo è minore del secondo non si fa niente, se il secondo è minore del primo si scambiano.
(passo induttivo) Si scorre tutto l'insieme effettuando scambi a coppie se il primo elemento è maggiore del secondo. Si procede finché tutto l'elenco non è ordinato. In pratica, si identifica al termine del primo ciclo l'elemeno più grande, poi il vice-più grande e così via |
| HeapSort | O(nlog(n)) | Utilizzando un heap si trasferisce la lista nell'heap e poi si rimuovono uno a uno gli elementi. Se max-heap si rimuove il più grande e si mette alla fine, se min-heap il contrario. |
| MergeSort | Θ(nlog(n)) | Algoritmo divide-et-impera (Impera) avendo due sequenze ordinate da fondere, basta estrarre di volta in volta l'elemento più piccolo tra i due elementi correnti delle due code e incrementare l'indice. (Divide) divide l'array in due parti uguali e applica il mergesort stesso a entrambe le metà. |
| QuickSort | O(n2) (caso peggiore), O(nlog(n)) (caso medio) | Algoritmo divide-et-impera (Impera) concatena i due pezzi di array divisi dalla parte divide. (Divide) divide l'array in due parti, in cui la prima contiene gli elementi ≥ x e la seconda gli elementi < x, dove x è un numero scelto casualmente. |
| IntegerSort
Nota: è detto anche CountingSort |
O(n+k), dove k è l'intero più grande dell'array | L'algoritmo usa un array A di appoggio di dimensione k, in cui a ogni elemento e dell'array di partenza incrementa A[e]. Alla fine scorre l'array A aggiungendo un elemento a ogni A[i] > 0 e decrementa A[i]. |
| BucketSort | O(n+k), dove k è l'intero più grande dell'array | L'algoritmo funziona in maniera molto simile a IntegerSort, ma ordina record invece che interi e quindi non può usare solo un array di interi ma deve usare una lista di record. |