Algoritmi di ordinamento comparativi
Un algoritmo di ordinamento comparativo è un tipo di algoritmo di ordinamento che esamina semplicemente gli elementi di una lista mediante una singola operazione di comparazione astratta (spesso un operatore "minore di" o "uguale a") per determinare di una coppia di elementi quale deve venir posizionato prima nella lista finale ordinata. L'unico requisito è che l'operatore soddisfi due delle proprietà di un ordine totale:
- se a ≤ b e b ≤ c allora a ≤ c (transitività)
- per ogni a e b, si ha che a ≤ b oppure b ≤ a (totalità o tricotomia).
È possibile che si verifichi sia che a ≤ b sia che b ≤ a (nel caso di a = b) : in questo caso ognuno dei due elementi può essere posizionato prima dell'altro. In un ordinamento stabile l'ordine di input degli elementi determina l'ordine degli elementi ordinati.
Per capire come funziona un algoritmo di ordinamento comparativo si può pensare al modo in cui ordinare un insieme di pesi da bilancia che non hanno indicazione del loro peso avendo a disposizione solo una bilancia. Lo scopo è quello di allineare i pesi secondo il loro peso potendo solo posizionare 2 pesi sui piatti della bilancia per vedere quale pesa di più (o se hanno lo stesso peso).
Esempi
Quello che segue è un elenco dei più noti algoritmi di ordinamento di tipo comparativo:
- Quick sort
- Heap sort
- Merge sort
- Intro sort
- Insertion sort
- Selection sort
- Bubble sort
Questi sono invece algoritmi non comparativi:
- Radix sort (esamina le singole cifre degli elementi)
- Counting sort (indicizza i dati)
- Bucket sort (divide gli elementi per intervalli di valore)
Note
- Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Seconda Edizione. Addison-Wesley, 1997. ISBN 0-201-89685-0. Sezione 5.3.1: Minimum-Comparison Sorting, pp. 180–197.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Seconda Edizione. MIT Press e McGraw-Hill, 2001. ISBN 0-262-03293-7. Sezione 8.1: Lower bounds for sorting, pp. 165–168.
V · D · M | ||
---|---|---|
Teoria | Teoria della complessità computazionale · Notazione O Grande · Array · Lista · Stack · Coda · Ordinamento comparativo · Ordinamento adattivo | |
Algoritmi a scambio | Bubble sort · Shaker sort · Odd-even sort · Comb sort · Gnome sort · Quicksort | |
Algoritmi di selezione | Selection sort · Heap sort · Smoothsort | |
Algoritmi ad inserimento | Insertion sort · Shell sort · Tree sort · Library sort · Patience sorting | |
Algoritmi a fusione | Merge sort · Timsort | |
Algoritmi non comparativi | Radix sort · Bucket sort · Counting sort · Pigeonhole sort | |
Altri algoritmi | Rete di ordinamento · Ordinamento topologico · Ordinamento bitonico · Ordinamento delle frittelle | |
Algoritmi inefficienti | Stupid sort · Trippel sort |