PROBLEMA DELL'ORDINAMENTO

Preso un insieme S, diciamo che questo è totalmente ordinato se in esso è definita una relazione d’ordine \le tale che \forall x,y \in S si ha che x \le y oppure y \le x.

Esempi di insiemi totalmente ordinati sono:

• \mathbb{N}\ , \mathbb{Z}\ , \mathbb{Q}\ , \mathbb{R}\ sono insiemi totalmente ordinati rispetto al \le
• \Sigma , alfabeto dov’è definito un ordine alfabetico
• \Sigma * insieme delle parole dell’alfabeto \Sigma
• \Sigma * è totalmente ordinato rispetto all’ordinamento lessicografico (l’ordine alfabetico su \Sigma definisce su \Sigma * l'ordine lessicografico).

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 \le 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

PROBLEMA DELL’ORDINAMENTO
Siano x_1, x_2, … , x_n elementi presi da un insieme totalmente ordinato secondo una relazione d’ordine \le (per esempio Z).
Il problema dell’ordinamento (sort) consiste nel determinare una permutazione \sigma degli elementi in modo che: x \sigma_1 \le x \sigma_2 \le … \le x \sigma_n
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).

ORDINAMENTO ADATTIVO
Solitamente un algoritmo di ordinamento sfrutta operazioni di confronto e scambio. Se tali operazioni vengono svolte in modo indipendente dai dati di input l'algoritmo viene definito non adattivo. Mentre se un metodo di ordinamento esegue diverse sequenze di operazioni in funzione del risultato dei confronti si ha un algoritmo adattivo.

STABILITA’ DI UN ALGORTIMO
Un metodo di ordinamento si dice stabile se preserva l'ordine relativo dei dati con chiavi uguali all'interno del file da ordinare.
Ad esempio se si ordina per anno di corso una lista di studenti già ordinata alfabeticamente, un metodo stabile produce una lista in cui gli alunni dello stesso anno sono ancora in ordine alfabetico, mentre un ordinamento instabile probabilmente produrrà una lista senza più alcuna traccia del precedente ordinamento.
La stabilità può essere forzata aggiungendo prima dell'ordinamento un piccolo indice a ciascuna chiave o allungando in qualche altro modo le chiavi sulle quali operare.

---

Torna a Programmazione e Lab.