Algoritmi di ordinamento comparativi

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca
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 ab e bc allora ac (transitività)
  2. per ogni a e b, si ha che ab oppure ba (totalità o tricotomia).

È possibile che si verifichi sia che ab sia che ba (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).

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:

Questi sono invece algoritmi non comparativi:


  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica