Definizioni di base

Siano:

• $U$ un insieme di elementi;
• $\leq \subseteq U*U$ una relazione d'ordine totale su U (riflessiva, transitiva, antisimmetrica)

Input: $X \in U^n$

Output: la sequenza X ordinata, i.e. X[i] ≤ X[i+1] per ogni 1 ≤ i ≤ n

• X in memoria centrale ↔ ordinamento interno
• X su memoria esterna ↔ ordinamento esterno

Identifichiamo due classi di algoritmi d'ordinamento:

• Confronti e scambi: le operazioni eseguite sui dati sono quelle di confronto, X[i] ≤ X[j], e assegnamento, X[i] := X[j];
• Digitali: le operazioni possono riguardare singoli (o gruppi di) bit della rappresentazione di ciascun elemento

Un metodo di ordinamento si dice:

• stabile se rispetta l'ordine relativo degli elementi di ugual valore;
• adattivo se i confronti effettuati dipendono dai dati

Equivalenza per confronti

Sia $\approx_c\subseteq U^n * U^n$ la relazione definita da $X \approx_c Y$ se e solo se