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

Vi sono varie classi di algortimi di ordinamento, i più noti ed utilizzati sono gli algoritmi di ordinamento per confronto (di cui fanno parte i famosi Bubble-Sort, Insertion-Sort, Merge-Sort, Heap-Sort, Quick-Sort, ecc.).

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 Omega(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.

Link esterni

• Una breve guida agli algoritmi di ordinamento e ricerca: http://epaperpress.com/sortsearchItalian/index.html (in italiano)

---

|