Algoritmi e programmazione/Gli algoritmi di ordinamento

Da WikiAppunti.
Jump to navigation Jump to search
Nota disambigua.svg Il titolo di questa pagina non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è 3. Gli algoritmi di ordinamento.
/Gli algoritmi di ordinamento}}  [[{{#ifcategory:Traduzioni||Algoritmi e programmazione|/Gli algoritmi di ordinamento}}/L'analisi di complessità degli algoritmi{{#ifcategory:Traduzioni|/Gli algoritmi di ordinamento||/Gli algoritmi di ordinamento}}|2. L'analisi di complessità degli algoritmi]]/Gli algoritmi di ordinamento}}  [[{{#ifcategory:Traduzioni|/Gli algoritmi di ordinamento|Algoritmi e programmazione|/Gli algoritmi di ordinamento}}|{{#ifcategory:Traduzioni||Algoritmi e programmazione|/Gli algoritmi di ordinamento}}]][[{{#ifcategory:Traduzioni||Algoritmi e programmazione|/Gli algoritmi di ordinamento}}/Grafi e alberi{{#ifcategory:Traduzioni|/Gli algoritmi di ordinamento||/Gli algoritmi di ordinamento}}|4. Grafi e alberi]]  /Gli algoritmi di ordinamento}}
  • 2 ordinamento interno: dati memorizzati in memoria centrale (accesso diretto ai dati → si ottimizza il numero di passi);
  • ordinamento esterno: dati memorizzati in memoria di massa (tempi di attesa più lunghi → si ottimizza il numero di accessi).
  • 3 ordinamento in loco: usa oltre al vettore da ordinare una quantità di memoria ausiliaria che non dipende dal numero di dati da ordinare.
  • ordinamento stabile: l'ordine degli elementi ripetuti eventuali è uguale tra input e output.

Classificazione per complessità[modifica | modifica sorgente]

  • <math>O\left(n^2\right)</math> (quadratico): semplici, iterativi, basati sul confronto (es. insertion sort, selection sort, bubble sort);
  • <math>O\left(n \sqrt n \right)</math> (es. shell sort);
  • <math>O\left(n \cdot \log{n} \right)</math> (linearitmico): ottimi ma più complessi perché ricorsivi (es. merge sort, quick sort, heap sort);
  • <math>O\left(n\right)</math> (lineare): basati sul calcolo, ma ipotesi restrittive sui dati, cioè possono essere usati solo con determinati dati (es. counting sort).

Limite inferiore della complessità asintotica nel caso peggiore per gli algoritmi di ordinamento basati sul confronto[modifica | modifica sorgente]

Gli algoritmi basati sul confronto non possono avere una complessità inferiore a <math>n\log{n}</math> (linearitmica), solo quelli basati sul calcolo:

<math>T\left(n\right) = \Omega \left( n \cdot \log{n} \right)</math>
Dimostrazione
Caso di 3 interi (a1, a2, a3).

Osservazioni:

  • 3! permutazioni possibili
  • 3 confronti nel caso peggiore

Caso di n interi
livello i numero di foglie 2i
0 1 = 20
1 2 = 21
2 4 = 22
  • osservazione: n! permutazioni possibili ≤ numero di foglie;
  • servono almeno <math>2^h</math> foglie per accomodare tutte le <math>n!</math> permutazioni possibili → <math>2^h \geq n!</math>;
  • tramite la relazione di Stirling <math>n! > {\left( {n \over e} \right)}^n</math>:
    <math>2^h > {\left( {n \over e} \right)}^n; \; \log_2{2^h} > \log{{\left( {n \over e} \right)}^n}; \; h > n \left( \log_2{n} - \log_2{e} \right) \Rightarrow T \left( n \right) = \Omega \left( n \log{n} \right) \quad n \rightarrow + \infty</math>[1]

Bubble sort (o exchange sort)[modifica | modifica sorgente]

Al 1º ciclo, confronta due elementi adiacenti, se necessario li scambia, quindi passa alla casella successiva → si ottiene solo che l'ultimo elemento a destra è il massimo, ma gli altri non sono ordinati, cioè il valore massimo è galleggiato a destra.

Il vettore si divide idealmente in due sottovettori → serve un doppio ciclo annidato:

  • sottovettore destro: inizialmente vuoto, contiene via via i massimi ordinati;
  • sottovettore sinistro: si svuota man mano.

Ottimizzazione: è possibile usare un flag per terminare prima il ciclo se non è stato effettuato alcuno scambio nel ciclo interno.

Selection sort[modifica | modifica sorgente]

Al 1º ciclo, scandisce il vettore, trova la posizione del minimo, e lo scambia con il 1º elemento. Pertanto è il sottovettore sinistro che si riempie in modo ordinato, man mano che il ciclo viene incrementato → il selection sort e il bubble sort sono degli algoritmi incrementali. Il ciclo interno cerca il minimo nel sottovettore destro.

Counting sort[modifica | modifica sorgente]

È un algoritmo stabile (va bene per le chiavi ripetute), ma non è un algoritmo in loco. Va a calcolare direttamente la posizione finale di un dato.

L'algoritmo crea il vettore delle occorrenze semplici, che contiene il numero di occorrenze nell'input del dato che corrisponde all'indice, e poi crea il vettore delle occorrenze multiple:

Vettori counting sort.png

Leggendo il vettore in input da destra verso sinistra, pone ogni elemento nella posizione memorizzata nel vettore delle occorrenze multiple, quindi decrementa il valore posizione:

Counting sort.png

Utilizza 3 vettori: il vettore di partenza, il vettore risultato, e il vettore delle occorrenze. La dimensione del vettore delle occorrenze dipende dall'intervallo a cui possono appartenere i dati → non è un ordinamento in loco.

Viene implementato con 4 cicli for → <math>T\left(n\right) = O\left( n + k \right)</math>: si considera non più solo la dimensione dei dati, ma anche la loro complessità k, che cresce linearmente con n, ma la complessità k non può tendere a infinito. Supponendo kn: <math>T\left(n\right) = O\left(n\right)</math>.

Note[modifica | modifica sorgente]

  1. La base del logaritmo scompare perché si sottointende la moltiplicazione per una costante per il cambio di base.
Nota disambigua.svg Il titolo di questa pagina non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è 3. Gli algoritmi di ordinamento.
/Gli algoritmi di ordinamento}}  [[{{#ifcategory:Traduzioni||Algoritmi e programmazione|/Gli algoritmi di ordinamento}}/L'analisi di complessità degli algoritmi{{#ifcategory:Traduzioni|/Gli algoritmi di ordinamento||/Gli algoritmi di ordinamento}}|2. L'analisi di complessità degli algoritmi]]/Gli algoritmi di ordinamento}}  [[{{#ifcategory:Traduzioni|/Gli algoritmi di ordinamento|Algoritmi e programmazione|/Gli algoritmi di ordinamento}}|{{#ifcategory:Traduzioni||Algoritmi e programmazione|/Gli algoritmi di ordinamento}}]][[{{#ifcategory:Traduzioni||Algoritmi e programmazione|/Gli algoritmi di ordinamento}}/Grafi e alberi{{#ifcategory:Traduzioni|/Gli algoritmi di ordinamento||/Gli algoritmi di ordinamento}}|4. Grafi e alberi]]  /Gli algoritmi di ordinamento}}