Per approfondire questo argomento, consulta la pagina Ordinamento (programmazione in C).

lezione Il problema dell'ordinamento
	Tipo: lezione
	Materia: Algoritmi e strutture dati

Un classico problema algoritmico consiste nell'ordinare una sequenza di n elementi. Per poter ordinare tale sequenza è necessario che gli elementi appartengano tutti a un insieme dove è definita una relazione d'ordine; ossia, presi due elementi a scelta, deve sempre essere possibile accertare quale venga prima e quale dopo. Dunque per poter ordinare è necessario che esista:

Una chiave per ogni elemento (ad esempio: la matricola di uno studente, il prezzo di un prodotto, la data di un acquisto ecc..)
Un metodo (che solitamente restituisce un intero) che definisca l'ordine tra due elementi (ad esempio: int strcmp(char *s1, char *s2) per le stringhe in C)

Proprietà degli algoritmi di ordinamento

Esistono alcune proprietà che un algoritmo può presentare che sono molto utili e possono venire sfruttate persino per creare altri algoritmi di ordinamento.

Stabilità

Un algoritmo di ordinamento si dice stabile se in presenza di due elementi con la medesima chiave (due acquisti nella stessa data ad esempio) non modifichi l'ordine con cui i due elementi si presentavano prima dell'ordinamento. Ad esempio se applicassimo a una lista di persone ordinate per nome, un algoritmo di ordinamento stabile, in modo tale da ordinare le persone in base al cognome, otterremmo un elenco in cui tutte le persone con lo stesso cognome sono ordinate per nome (come nei normali elenchi telefonici). Se tale algoritmo non fosse stabile le persone con lo stesso cognome sarebbero disposte "casualmente" rispetto al nome. Non ha senso parlare di stabilità quando l'elemento rappresenta la propria chiave, ad esempio in un array di interi due '14' non sono distinguibili l'uno dall'altro dunque anche se venissero scambiati non potremmo accorgercene.

Sul posto (o "in loco")

Un algoritmo di ordinamento su array si dice sul posto se in ogni dato istante al più è allocato un numero costante di variabili, oltre all'array da ordinare: un algoritmo, quindi, è sul posto se non utilizza array di supporto. Si parla solo di array, perché in una lista concatenata, lo spazio occupato è già doppio rispetto al numero di elementi (un valore per l'elemento e un puntatore per il prossimo).

Algoritmi di ordinamento per confronto

In questa prima parte tratteremo soltanto di algoritmi di ordinamento per confronto, ossia che confrontano tra di loro, due elementi alla volta. Vedremo che, in alcuni casi, non è necessario confrontare gli elementi tra di loro. Ad esempio, come si fa a ordinare un mazzo di 52 carte?

Algoritmi di ordinamento "poco efficienti"

Esistono almeno tre algoritmi molto facili e di complessità temporale $\Theta (n^{2})$ : (sotto assunzione di costo uniforme)

Bubble sort
Selection sort
Insert sort

Per completezza vedremo brevemente gli ultimi due algoritmi, analizzandone la complessità nei casi ottimo, peggiore e medio (quest'ultimo sotto assunzione di distribuzione uniforme)

Selection Sort

Informalmente l'algoritmo può essere descritto nel seguente modo: si cerca il minimo della sequenza ancora da analizzare e lo si scambia con il primo elemento ancora da analizzare fino a che non resta soltanto un elemento.

L'animazione "salta" un passaggio, ossia la ricerca del minimo che ha complessità lineare (in tutti i casi: peggiore, migliore o medio). Dunque per ogni elemento (in realtà l'ultimo elemento è già in ordine, dunque n-1 volte) viene ripetuta la ricerca del minimo. La prima volta si cercherà su n elementi, la seconda su n-1, la terza su n-2... Dunque la complessità è determinata dalla somma

$\sum _{i=n}^{1}i=\sum _{i=1}^{n}i={\frac {n(n+1)}{2}}$

Dunque il selection sort ha complessità temporale (per tutti i casi) quadratica. Ossia $T_{p}(n)=T_{m}(n)=T_{a}(n)=\Theta (n^{2})$ Dove $T_{p}(n),T_{m}(n),T_{a}(n)$ sono rispettivamente il tempo impiegato nel caso peggiore, migliore e medio. Il selection sort non è stabile poiché può invertire l'ordine di elementi della stessa chiave (il lettore può provare a trovare un esempio in cui tale algoritmo non sia sul posto). È sul posto' poiché utilizza solo poche variabili locali (e non è ricorsivo). La proprietà più interessante del selection sort è quella che la parte già "analizzata" è ordinata, infatti da 0 a i l'array è ordinato, nessun elemento verrà aggiunto in quella parte. Ne diamo una versione in Java:

public static void ssort(int[] a) {
    int n = a.length;
    for(int i = 0; i < n-1; i++) {        
        scambia(a, i, indiceMinimoDa(a, i));
    }
}

static int indiceMinimoDa(int[] a, int k) { 
    int iMin = k;                             
    for(int i = k+1; i < a.length; i++)       
        if(a[i] < a[iMin]) iMin = i;            
    return iMin;                                            
}

Insertion Sort

L'insertion sort è un algoritmo di ordinamento che si basa sull'inserimento di un elemento all'interno di un array ordinato.

Inizialmente si considera il primo elemento come un array ordinato; si prosegue inserendo il secondo elemento al posto giusto: se è maggiore rimane dov'è se è minore (del primo elemento) si scambia. Così avanti come mostra l'animazione

L'algoritmo di inserimento deve scorrere in media metà array prima di trovare la posizione giusta per l'elemento da inserire. Nel caso peggiore dovrà scorrerlo tutto fino in fondo (se l'elemento era più piccolo di tutti quelli già inseriti), nel caso migliore dovrà effettuare solo un controllo (se è più grande di tutti quelli già inseriti). La sommatoria che descrive il caso medio è così definita

$\sum _{i=1}^{n}{\frac {i}{2}}={\frac {1}{2}}\sum _{i=1}^{n}i={\frac {n(n+1)}{4}}$

Dunque anch'essa quadratica (analogo discorso per il caso peggiore). Il caso migliore invece (che si presenta quando l'array è già ordinato) è lineare.

Dunque l'algoritmo di ordinamento ha la seguente complessità:

Caso peggiore: $T_{p}(n)=\Theta (n^{2})$ (Array ordinato all'inverso)

Caso medio: $T_{a}(n)=\Theta (n^{2})$

Caso migliore: $T_{m}(n)=\Theta (n)$ (Array ordinato)

Anche in questo caso ne diamo una versione in Java:

public static void isort(int[] a){
    int j;
    for (int i =1;i<a.length;i++){
        int t = a[i];
        j=i;
        while(j>0 && t<a[j-1]){
            a[j]=a[j-1];
            j--;
            }
        a[j]=t;
    } 
}

Algoritmi di ordinamento efficienti

Merge Sort

Il merge sort è il primo algoritmo d'ordinamento ricorsivo che vediamo. Se ne può dare anche una versione iterativa di cui, però, vedremo soltanto il codice per completezza di trattazione. (Nota lessicale, d'ora in poi utilizzerò il termine "sequenza" sia per indicare array sia liste concatenate; il mergesort può essere applicato, con le dovute precauzioni a entrambi i tipi astratti).

Il merge sort è un algoritmo di tipo "Divide et Impera", ossia è diviso in due parti:

"Divide" Dividere la sequenza in due parti (operazione banale per gli array, più complicata per una lista)
"Impera" Fondi le due sequenze in una che contiene tutti gli elementi in ordine.

Il mergesort per "fondere" le due sequenze utilizza, ovviamente, l'algoritmo di merge. Lo studente, a questo punto del corso dovrebbe sapere come funziona l'algoritmo di merge, ne faremo comunque una breve analisi.

Date due sequenze, S1 e S2, ordinate, per ottenere S3, anch'essa sequenza ordinata e tale che ogni elemento di S1 e S2 appartenga a S3 si scorrono S1 e S2 inserendo in S3 l'elemento più piccolo tra le due. Una volta terminata S1 (o S2) si completa inserendo in S3 i rimanenti elementi di S2 (o S1).

Nel mergesort S1 e S2 sono solitamente due sequenze interne alla sequenza originale, per identificarle servono quindi almeno 3 indici. La sequenza target deve essere un essere dichiarata e allocata a parte, poiché non è possibile riscrivere gli elementi sulla sequenza di partenza (quantomeno non è facile realizzare un algoritmo senza sequenza di appoggio).

Diamo qui un'implementazione del merge in Java

private static void merge(int[] a, int left, int mid, int right, int[] h) {
    //a ordinato da [left, mid] e [mid+1, right]
    int x = left;
    int y = mid + 1;
    int n = left;
    if (left>mid || mid>=right || a[mid] <= a[mid + 1]) {
        return;
    }
    while (x <= mid && y <= right) {
        if (a[x] <= a[y]) {
            h[n++] = a[x++];
        } else {
            h[n++] = a[y++];
        }
    }
    while (x <= mid) {
        h[n++] = a[x++];
    }
    while (y <= right) {
        h[n++] = a[y++];
    }
    for (int i = left; i <= right; i++) {
        a[i] = h[i];
    }
}

Il mergesort quindi, divide in due la sequenza da ordinare fino a che non rimane solo un elemento (che è ordinato), successivamente fonde i singoli elementi creando gruppi di due, i quali a loro volta verranno fusi tra loro creando la sequenza finale ordinata.

In pseudo codice il Mergesort può essere descritto così:

MergeSort(sequenza S){
    if(lunghezza(S) >1){
        S1, S2 <-- Dividi (S)
        MergeSort(S1)
        MergeSort(S2)
        S <-- Merge(S1, S2)
    }
}

Analizzando il caso in cui la sequenza è costituita da un array, possiamo notare come il lavoro sia effettuato esclusivamente dal merging, infatti dividere un array in due significa semplicemente scegliere l'indice medio. In una lista, invece, dividere a metà significa scorrere la lista almeno una volta (facendo saltare alternativamente i puntatori), con complessità lineare. In entrambi i casi, il merge ha una complessità lineare alla somma della lunghezza delle due sequenze (dunque la divisione della lista non influisce asintoticamente sulla complessità dell'algoritmo). Notare inoltre che il merge ha solo un caso migliore (lo studente cerchi di trovarlo dal codice dato sopra), perciò anche il mergesort presenterà solo un caso migliore (un array ordinato), mentre il caso medio corrisponderà a quello peggiore. L'equazione di ricorrenza (si veda le lezioni sulla ricorsione), per il caso peggiore e medio, sono le seguenti

\left\{{\begin{matrix}T(1)=1\\T(n)=2(T/2)+n\end{matrix}}\right.

Possiamo provare a risolverla manualmente per sostituzioni successive. (Vedremo in seguito il master theorem per risolvere questo tipo di equazioni).

${\begin{aligned}T(n)&=2T(n/2)+n&T(n/2)=2T(n/2^{2})+(n/2)\\&=2(2T(n/2^{2})+(n/2))+n=\\&=2^{2}T(n/2^{2})+2n=\\&=2^{2}(2T(n/2^{3})+(n/2^{2}))+2n=\\&=2^{3}T(n/2^{3})+3n\\&{\mbox{Dopo k passi:}}\\&=2^{k}T(n/2^{k})+kn&T(n/2^{k})=T(1)\Rightarrow n/2^{k}=1\\&=n+(log_{2}n)\cdot n&2^{k}=n,k=log_{2}n\\&=n(1+log_{2}n)=\Theta (n\cdot log_{2}n)\end{aligned}}$

Questa non è una vera e propria dimostrazione tuttavia, il risultato è giusto e se ne può dare una dimostrazione induttiva a posteriori.

Il caso migliore, che si presenta quando l'array è già ordinato, e il merge non fa niente, ha complessità lineare.

Dunque il mergesort ha complessità $\Theta (n\cdot log(n))$ : migliore (di gran lunga migliore) di tutti gli algoritmi visti fino a qui. Il mergesort è stabile: nel merge è fondamentale la riga if (a[x] <= a[y]), infatti l'uguale permette di scegliere sempre per primo l'elemento di sinistra, ossia quello che, precedentemente all'ordinamento, veniva prima di un altro elemento, eventualmente con chiave uguale. Il megersort non è sul posto: oltre a essere ricorsivo (e quindi occupare spazio sullo stack) è necessario un array ausiliare; la complessità spaziale del merge è dunque $\Theta (n)$ .

Essendo la versione ricorsiva molto facile da implementare, mostriamo solo la versione iterativa in Java:

public static void msortI(int[] a){
	int i, p,e,m;	
	int N = a.length;
	int[] helper = new int[N];
	i=0;
	p=1;
	while(p<N){		
		while(i<N){
			m = (i+p) >=N ? N : i+p;
			e = (i+2*p)>=N ? N : i+2*p;
			merge(a,i,m-1,e-1,helper);
			i+=2*p;
		}			
		p*=2;
		i=0;	
        }
}

Quick Sort

Il quickSort è un altro algoritmo di ordinamento ricorsivo che come il merge sort è basato sul paradigma divide et impera. Esso opera nel seguente modo:

Divide: partzionare l'array ${\begin{aligned}A[p..r]\end{aligned}}$ in due sottoarray ${\begin{aligned}A[p..q-1]\end{aligned}}$ e ${\begin{aligned}A[q+1..r]\end{aligned}}$ (eventualmente vuoti) tali che ogni elemento di ${\begin{aligned}A[p..q-1]\end{aligned}}$ sia minore o uguale ad ${\begin{aligned}A[q]\end{aligned}}$ che, a sua volta, è minore o uguale a ogni elemento di ${\begin{aligned}A[q+1..r]\end{aligned}}$ . Calcolare l'indice q come parte di questa procedura di partizionamento.
Impera: ordinare i due sottoarray ${\begin{aligned}A[p..q-1]\end{aligned}}$ e ${\begin{aligned}A[q+1..r]\end{aligned}}$ chiamando ricorsivamente quicksort.
Combina: Poiché sottoarray sono già ordinati, non occorre alcun lavoro per combinarli: l'intero array ${\begin{aligned}A[p..r]\end{aligned}}$ è ordinato.

In pseudocodice la quicksort può essere descritto così:

QuickSort(lista A, int p, int r){
    if (p < r){
       q = Partition(A,p,r)
       QuickSort(A,p,q-1)
       QuickSort(A,q+1,r)
   }
}

Partizionare l'array

L'elemento chiave dell'algoritmo è la procedura Partition, che riarrangia il sottoarray ${\begin{aligned}A[p..r]\end{aligned}}$ sul posto.

 Partition(lista A, int p,int r){
     x = A[r]
     i = p - 1
     for (j = p to r-1){
        if (A[j] <= x){
          i = i+1
          scambia A[i] con A[j]
        }
     }
     scambia A[i+1] con A[r]
     return i+1
  }

La procedura partition comincia ponendo come pivot l'ultimo elemento dell'array. Durante l'esecuzione della procedura l'array verrà suddiviso in quattro regioni:

nella prima regione ci sono tutti quegli elementi dell'array che già stati confrontati con pivot e sono minori o uguali del pivot stesso;
nella seconda regione ci sono gli elementi che sono già stati confrontati e sono maggiori del pivot stesso;
nella terza regione sono tutti gli elementi non sono ancora stati confrontati con il pivot;
mentre nella quarta regione vi è il pivot stesso.

Si può facilmente intuire che il tempo di esecuzione della procedura Partition è di ${\begin{aligned}\Theta (n)\end{aligned}}$ , dove ${\begin{aligned}n=r-p+1\end{aligned}}$ .

Prestazioni di QuickSort

Il tempo di esecuzione di Quicksort dipende dal fatto che il partizionamento sia bilanciato o sbilanciato e questo, sua volta dipende da quali elementi vengono utilizzati per il partizionamento. Se il partizionamento è bilanciato, l'algoritmo viene eseguito con la stessa velocità asintotica di merge sort, se il partizionamento è sbilanciato invece quicksort può essere asintoticamente lento quanto insertion sort.

Partizionamento nel caso peggiore

Il comportamento nel caso peggiore di Quicksort si verifica quando la routine di partizionamento produce un sotto problema con n-1 elementi e uno con 0 elementi. Supponiamo che questo sbilanciamento si verifichi in ogni chiamata ricorsiva: il partizionamento costa ${\begin{aligned}\Theta (n)\end{aligned}}$ interni tempo. Poiché per una chiamata ricorsiva su un'altra vuota ${\begin{aligned}T(0)=\Theta (1)\end{aligned}}$ di una ricorrenza per il tempo di esecuzione può essere espressa così:

${\begin{aligned}T(n)&=T(n-1)+T(0)+\Theta (n)\\&=T(n-1)+\Theta (n)\end{aligned}}$

Intuitivamente, se sommiamo i costi a ogni livello della ricorsione, otteniamo una serie artimetica il cui valore è ${\begin{aligned}\Theta (n^{2})\end{aligned}}$ .Quindi se lo sbilanciamento delle due partizioni è massimo a ogni livello ricorsivo dell'algoritmo, il tempo di esecuzione è ${\begin{aligned}\Theta (n^{2})\end{aligned}}$ .

Partizionamento nel caso migliore

Nel caso di bilanciamento Massimo, Partition produce due sottoproblemi, ciascuno di dimensione non maggiore di ${\begin{aligned}n/2\end{aligned}}$ in questo caso quicksort viene eseguito molto più velocemente. La ricorrenza per il tempo di esecuzione è

${\begin{aligned}T(n)<=2T(n/2)+\Theta (n)\end{aligned}}$

e utilizzando il teorema dell'esperto si ottiene la soluzione ${\begin{aligned}T(n)=\Theta (n\cdot log_{2}(n))\end{aligned}}$

Partizionamento Bilanciato

Albero di ricorsione ripartizione 9/10 1/10

Il tempo di esecuzione del caso meglio di quicksort è molto più vicino al caso migliore che al caso peggiore. Per capire perché dobbiamo comprendere come il bilanciamento del partizionamento influisce sulla ricorrenza che descrive il tempo di esecuzione. Supponiamo per esempio che l'algoritmo di partizionamento produca sempre una ripartizione proporzionale 9 a 1, che a prima vista potrebbe sembrare molto sbilanciata. In questo caso, otteniamo la ricorrenza:

${\begin{aligned}T(n)<=T(9n/10)+T(n/10)+cn\end{aligned}}$

Come si vedono da albero di ricorsione ogni livello dell'albero un costo ${\begin{aligned}cn\end{aligned}}$ , finché non viene raggiunta una condizione al contorno alla profondità ${\begin{aligned}log_{1}0(n)=\Theta (log_{2}(n))\end{aligned}}$ , dopo la quale livelli hanno al massimo un costo ${\begin{aligned}cn\end{aligned}}$ .La ricorsione termina la profondità ${\begin{aligned}log_{(}10/9)(n)\end{aligned}}$ . il costo totale di Quicksort è dunque ${\begin{aligned}O(n\cdot log_{2}(n))\end{aligned}}$ . Pertanto con una ripartizione proporzionale 9 a 1 a ogni livello di ricorsione Quicksort viene eseguito ${\begin{aligned}O(n\cdot log_{2}(n))\end{aligned}}$ .

Partizionamento nel caso Medio

Per quanto riguarda il caso medio dobbiamo fare alcune considerazioni. La prima considerazione è che il costo di Quicksort non dipende dai valori dell'array ma dipende dagli ordini degli elementi.Quando eseguiamo Quicksort su un Array di input casuale,è poco probabile che il partizionamento venga sempre nello stesso modo e a qualsiasi livello, come abbiamo ipotizzato nella nostra analisi informale. E’ logico supporre, invece, che qualche ripartizione sarà ben bilanciata e qualche altra sarà molto sbilanciata.

Supponiamo, ai fini dell'intuizione, che le partizioni buone e cattive si alternino nei vari livelli dell'albero e che quelle buone siano le ripartizioni nel caso migliore e quelle cattive siano le ripartizioni nel caso peggiore. La combinazione cattiva seguita dalla ripartizione buona produce tre sottoarray di dimensioni ${\begin{aligned}0,(n-1)/2-1\end{aligned}}$ e ${\begin{aligned}(n-1)/2\end{aligned}}$ con un costo di partizionamento complessivo pari a ${\begin{aligned}\Theta (n)+\Theta (n-1)=\Theta (n)\end{aligned}}$ . Certamente, questo caso non è peggiore di quello del caso peggiore, ovvero un unico livello di partizionamento genera due sottoarray dimensione ${\begin{aligned}(n-1)/2\end{aligned}}$ con un costo di ${\begin{aligned}\Theta (n)\end{aligned}}$ . Ma quest'ultimo caso è bilanciato! Intuitivamente, il costo di ${\begin{aligned}\Theta (n-1)\end{aligned}}$ della ripartizione cattiva può essere assorbito dal costo di ${\begin{aligned}\Theta (n)\end{aligned}}$ della ripartizione buona, quindi la ripartizione risultante è buona. In definitiva, il tempo di esecuzione di Quicksort, quando i livelli si alternano fra buone cattive ripartizioni, è come il tempo di esecuzione nel caso in cui ripartizioni siano soltanto buone: ancora ${\begin{aligned}O(n\cdot log_{2}(n))\end{aligned}}$ .

Versione Randomizzata di Quicksort

Nell'analisi del comportamento di quicksort nel caso meglio, ante abbiamo fatto l'ipotesi che tutte le permutazioni dei numeri di input fossero ugualmente probabili. Nella pratica, però, non possiamo aspettarci che questo sia sempre vero. A volte è possibile aggiungere la randomizzazione a un algoritmo per ottenere una buona prestazione attesa con tutti gli input.

Il metodo di randomizzazione che si è adottato detto campionamento casuale. Anziché utilizzare sempre l'ultimo elemento come pivot, utilizzeremo un elemento scelto a caso dal sottoarray ${\begin{aligned}A[p..r]\end{aligned}}$ . Per fare questo scambieremo l'ultimo con un elemento dell'array con un elemento scelto a caso all'interno dell'array ${\begin{aligned}A[p..r]\end{aligned}}$ questa modifica, con la quale campioniamo a caso un intervallo dell'array ci assicura che l'elemento pivot avrà la stessa possibilità di essere uno dei qualsiasi elementi da sottoarray ${\begin{aligned}A[p..r]\end{aligned}}$ . Poiché il pivot viene scelto a caso ti aspettiamo che la ripartizione della array di input sia ben bilanciata in media.

Ecco lo pseudo codice della nuova procedura RandomizedPartition:

  RandomizedPartition(lista A,int p,int r){
     i = Random(p,r)
     scambia A[r] con A[i]
     return Partition(A,p,r)
  }

Il nuovo Quicksort chiama RandomizedPartition anziché Partition:

  RandomizedQuicksort(lista A, int p,int r){
      if(p<r){
          q = RandomizedPartition(A,p,r)
          RandomizedQuicksort(A,p,q-1)
          RandomizedQuicksort(A,q+1,r)
      }
  }

Tempo di esecuzione Atteso

Per gli algoritmi randomizzati, dato che loro stessi effettuano delle scelte casuali, si parla di tempo di esecuzione atteso. Si è già data una spiegazione intuitiva sul perché il tempo di esecuzione di RandomizedQuicksort sia ${\begin{aligned}O(n\cdot log_{2}(n))\end{aligned}}$ : se, in ogni livello di ricorsione, la ripartizione introdotta da RandomizedPartition pone una frazione costante qualsiasi degli elementi in un lato della ripartizione, allora l'albero di ricorsione ha profondità ${\begin{aligned}\Theta (log_{2}(n))\end{aligned}}$ e in ogni livello viene svolto un lavoro di ${\begin{aligned}O(n)\end{aligned}}$ . Anche se aggiungiamo qualche nuovo livello con la ripartizione più sbilanciata possibile tra questi livelli il tempo totale resta: ${\begin{aligned}O(n\cdot log_{2}(n))\end{aligned}}$ .

Ordinamento in tempo lineare

Gli algoritmi precedentemente introdotti possono ordinare n numeri nel tempo di $O(n\cdot log_{2}(n))$ . Merge sort raggiunge questo limite superiore nel caso peggiore, mentre Quick sort lo raggiunge nel caso medio. Questi algoritmi condividono un'interessante proprietà: l'ordinamento che effettuano è basato soltanti sui confronti fra gli elementi di input. Infatti questi algoritmi sono detti ordinamenti per confronti.

Albero di decisione

Gli ordinamenti per confronti possono essere visti astrattamente in termini di alberi di decisione. Un albero di decisione è una albero binario pieno che rappresenta i confronti fra gli elementi che vengono effettuati da un particolare algoritmo di ordinamento che opera su un input di una data dimensione.

In un albero di decisione, ogni nodo è annotato con $i:j$ per qualche $i$ e $j$ nell'intervallo $1\leq i\leq j\leq n$ , dove $n$ è il numero di elementi della sequenza di input. Ogni foglia è annotata con una permutazione dell' array di input: $\left\langle \pi (1),\pi (2),...\pi (n)\right\rangle$ . L'esecuzione dell'algoritmo di ordinamento consiste nel tracciare un cammino dalla radice dell'albero fino a una foglia. Il sottoalbero sinistro rappresenta il confronto $a_{i}\leq a_{j}$ , mentre il sottoalbero destro rappresenta il confronto $a_{i}>a_{j}$ .

Poiché qualsiasi algoritmo di ordinamento corretto deve essere in grado di produrre ogni permutazione del suo input, una condizione necessaria affinché l'algoritmo di ordinamento sia corretto è che che ciascuna delle $n!$ permutazioni del suo input di $n$ elementi appaia come una delle foglie dell'albero di decisione, e che ciascuna di queste foglie sia raggiungibile dalla radice attraverso un percorso che corrisponde all'effettiva esecuzione dell'algoritmo di ordinamento.

Limite inferiore per l'ordinamento per confronti

La lunghezza del percorso più lungo dalla radice di un albero di decisione a una delle sue foglie raggiungibili rappresenta il numero di confronti che svolge il corrispondente algoritmo nel caso peggiore. Di conseguenza, il numero di confronti nel caso peggiore per un dato algoritmo di ordinamento è data dall'altezza del suo albero di decisione.

Teorema

Qualsiasi algoritmo di ordinamento per confronti richiede $\Omega (n\cdot log_{2}n)$ confronti nel caso peggiore.

Dimostrazione

Consideriamo l'albero di decisione, di un algoritmo di ordinamento, dove ogni permutazione dell'input appare come foglia raggiungibile. L'albero di decisione possiede un'altezza h e ha n foglie raggiungibili, quindi corrisponderà a un ordinamento per confronti di n elementi. Poiché ciascuna delle $n!$ permutazioni dell'input compare in una foglia, si ha $n!\leq l$ . Dal momento che un albero binario di altezza h non ha più di $2^{h}$ foglie, si ha

$n!\leq l\leq 2^{h}$

Prendendo i logaritmi, questa relazione implica che

${\begin{aligned}h&\geq log_{2}(n!){\mbox{ (perchè la funzione log è monotonicamente crescente)}}\\&=\Omega (n\cdot log_{2}(n)){\mbox{ (utilizzando l'approssimazione di Stirling)}}\end{aligned}}$

Counting Sort

L'algoritmo Counting sort è un algoritmo di ordinamento che suppone che ciascuno degli n elementi di input sia un numero intero compreso nell'intervallo da 0 a k, per qualche intero k. Counting sort determina, utilizzando un array di appoggio, per ogni elemento di input x, il numero di elementi minori di x. Esso usa questa informazione per inserire l'elemento x direttamente nella sua posizione nell'array di output.

Funzionamento

Piuttosto che utilizzare i confronti per ordinare l'array, counting sort utilizza un array di appoggio C di dimensione k a cui inizialmente assegnerà le occorrenze dell'i-esimo numero dell'array da ordinare. Utilizzando queste informazioni determina per ogni $i=1,...,k$ quanti elementi di input sono minori o uguali a l'i-esimo elemento, mantenendo la somma corrente in C. Infine scorrerà l'array di input dalla fine all'inizio e posizionerà i valori da ordinare in B, utilizzando il vettore C.

Un'importante proprietà di counting sort è la stabilità: i numeri con lo stesso valore si presentano nell'array di output nello stesso ordine in cui si trovavano nell'array di input.

Pseudo codice

 countingSort(lista A, lista B,int k){
     C = new Array(k)
     //Inizializzo C
     for i = 0 to k
         C[i] = 0
    
    //Conto le occorenze del j-esimo elemento nell'array A
    for j = 1 to A.length
         C[A[j]] = C[A[j]] + 1
    
    //Determino quanti sono gli elementi di A <= del i-esimo elemento 
    for i = 1 to k
         C[i] = C[i] + 1
    
    //Riordino l'array a utilizzando l'array C
    for j = A.length downto 1
         B[C[A[j]]] = A[j]
         C[A[j]] = C[A[j]] - 1
  }

Prestazioni di Counting sort

Notiamo che l'algoritmo esegue 4 cicli for: il primo ciclo for impiega un tempo di $\Theta (k)$ , il secondo ciclo impiega un tempo di $\Theta (n)$ , il terzo ciclo impiega un tempo di $\Theta (k)$ mentre il quarto impiega un tempo di $\Theta (n)$ . Quindi il tempo totale è $\Theta (k+n)$ . Di solito counting sort viene utilizzato quando $k=O(n)$ (cioè quando k è dello stesso ordine di grandezza di n), dove il tempo di esecuzione diventa $\Theta (n)$ .

Come si può vedere counting sort batte il limite inferiore $\Omega (n\cdot log_{2}(n))$ dimostrato precedentemente. Questo è dovuto al fatto che l'algoritmo non effettua nessun tipo di confronto, piuttosto usa i valori effettivi degli elementi come indici di un array. Il limite inferiore $\Omega (n\cdot log_{2}(n))$ non vale se ci si allontana dal modello di ordinamento per confronti.

Quando Counting sort è inefficiente

Quando $k$ risulta essere molto più grande della dimesione dell'array $n$ , l'algoritmo non risulta essere efficiente dato che perderà molto tempo nel primo e terzo ciclo. In particolare se $k=O(n^{3})$ il tempo di esecuzione di counting sort risulta essere peggiore del tempo di esecuzione di algoritmi come Bubble sort o Selection sort.

Radix sort

Radix Sort è un algoritmo di ordinamento non in loco. L'algoritmo utilizza un procedimento contro intuitivo per l'uomo, ma più facilmente implementabile. Esegue gli ordinamenti per posizione della cifra, ma partendo dalla cifra meno significativa. E’ essenziale, però che gli ordinamenti delle cifre in questo algoritmo siano stabili, altrimenti radix Sort non ordinerà la lista.

Pseudo codice

   radixSort(lista A, int d){
   //d è in numero massimo di cifre da ordinare
        for i = 1 to d
           usa un ordinamento stabile per ordinare l'array A sulla cifra i
   }

Prestazione di Radix sort

Dati $n$ numeri di $d$ cifre, dove ogni cifra può avere fino a $k$ valori possibili, la procedura Radix Sort, se utilizza Counting Sort come algoritmo di ordinamento stabile, ordina correttamente i numeri nel tempo di $\Theta (d(n+k))$ . Quando $d$ è costante e $k=O(n)$ , radix Sort viene eseguito un tempo lineare. Più In generale, abbiamo una certa flessibilità sul modo in cui ripartire le singole chiavi in cifre.

Bucket Sort

Bucket sort è è un algoritmo di ordinamento in loco che presuppone che un input sia estratto da una distribuzione uniforme. Come Counting sort, Bucket sort è veloce perché fa un'ipotesi sull'input: esso suppone che gli input sia generato da un processo casuale che distribuisce gli elementi uniformemente e indipendentemente nell'intervallo $[0,1)$ .

Funzionamento

Bucket Sort divide l'intervallo $[0,1)$ in $n$ sottointervalli della stessa dimensione chiamati bucket. Il primo passo che l'algoritmo compie è di porre ciascun elemento dell'array nel bucket di appartenenza; successivamente, utilizzando un altro algoritmo di ordinamento, ordina tutti i bucket presenti; l'ultimo passo sarà quello di concatenare ciascun bucket per ottenere l’array ordinato. Dato che l'algoritmo assume che l'input sia uniformemente e indipendentemente distribuito nell’intervallo $[0,1)$ non si aspetta che molti numeri vanno a finire allo stesso bucket, e ciò contribuisce a rendere Bucket sort un algoritmo molto efficiente.

Pseudocodice

    bucketSort(A,n)
       B = new Array(n-1)
       
       //Crea buckets
       for i = 0 to n
           B[i] = []
       
       //Inserisce ciascun elemento nel proprio bucket di appartenenza
       for j = 0 to A.length
           index_bucket = Math.floor(A[j])
           B[index_bucket = A[j]
           
       //Ordina i singoli Bucket 
       for i = 0 to n
           insertionSort(B[i])
            
       //concatena i bucket
       k = 0
       for i = 0 to n
           for j = 0 to B[i].length
               A[k] = B[i][j]
               k++
       
        return A

Prestazioni di Bucket sort

Per il tempo di esecuzione, notiamo che l'algoritmo possiede 3 cicli for richiedono un tempo di $O(n)$ è nel caso peggiore. Resta da valutare il tempo totale richiesto dalla $n$ chiamate a insertion Sort.