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.