Algoritmo di ordinamento

Un algoritmo di ordinamento è un algoritmo che viene utilizzato per ordinare (in ordine crescente o decrescente) gli elementi di un insieme (in genere una lista o un array).

La relazione d'ordine che intercorre tra gli elementi dell'insieme può essere:

• quella banale per l'insieme preso in considerazione (ad esempio la relazione di <= per l'insieme dei numeri naturali)
• una relazione definita dal programmatore stesso nel caso in cui il tipo degli elementi dell'insieme sia un tipo definito dall'utente o che comunque non abbia una relazione di ordinamento predefinita

La ricerca e l'ottimizzazione di algoritmi di ordinamento è molto importante in ambito informatico e per queste classi di algoritmi sono stati dimostrati svariati teoremi che ne definiscono i limiti. Il più importante è il seguente:

Teorema: Dato un qualsiasi algoritmo di ordinamento per confronto, la sua complessità di tempo è un Ω(NlogN).

Avendo i concetti base della teoria della complessità computazionale si capisce bene che questo teorema fissa il limite inferiore di "performance" di tali algoritmi per cui nessun algoritmo di ordinamento per confronto avrà una complessità minore di questa. Nulla è noto su altri tipi di ordinamento, nemmeno quali possano essere. Vi sono forti indizi che un ordinamento totalmente quantistico possa avere un più basso limite inferiore, dato che in ogni altro tipo di algoritmo è così, tuttavia non è noto come possa essere implementato senza ricorrere al confronto tra elementi.

Elenco degli algoritmi di ordinamento

Vi sono varie classi di algoritmi di ordinamento, i più noti ed utilizzati sono gli algoritmi di ordinamento per confronto:

• Bubble sort
• Shaker sort
• Insertion sort
• Pigeonhole sort
• Bucket sort
• Counting sort
• Merge sort
• B-Tree sort
• Radix sort
• Stupid sort
• Gnome sort
• Shell sort
• Selection sort
• Comd sort
• Heap sort
• Smoothsort
• Quicksort
• Introsort
• Several unique sort

Nel 2001 è stato trovato un algoritmo quantistico che ha complessità Ω(log₃N).

Collegamenti esterni

• Una breve guida agli algoritmi di ordinamento e ricerca (in italiano)
• Algoritmi quantistici (in inglese)

Algoritmo di ordinamento

See also: Algoritmo di ordinamento, 2001, Algoritmo, Array, Bubble sort, Informatica, Informatica quantistica, Insertion sort, Lingua inglese, Lingua italiana