Algoritmi di ordinamento comparativi

Per ordinare un insieme di pesi senza l'indicazione del peso ma disponendo solo di una bilancia si usa un algoritmo di ordinamento di tipo comparativo.

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:

1. se a ≤ b e b ≤ c allora a ≤ c (transitività)
2. 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

Il Bubble sort è un algoritmo di ordinamento che scorre continuamente una lista di dati e scambia gli elementi fra di loro finché essi non sono nell'ordine corretto.

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.