Ordinamento

Appunti introduttivi su proprieta', esempi e complessita' degli algoritmi di ordinamento.

Attributi degli algoritmi

• Ordinamento interno ed esterno: se i dati stanno in memoria, il metodo e' interno.
• Algoritmo in place: non crea una copia dell'input per raggiungere l'obiettivo.
• Algoritmo stabile: preserva l'ordine relativo dei dati con chiavi uguali.
• Algoritmo online: puo' operare anche su dati forniti uno alla volta.

Esempi

Algoritmi semplici

Insertion sort, selection sort e bubble sort sono esempi classici di algoritmi quadratici adatti alla didattica.

O(n^2) in media e nel caso pessimo
In place: spesso si
Stable: dipende dall'algoritmo