FANDOM


Nota disambigua
Il titolo di questa voce non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è 3. Gli algoritmi di ordinamento.
Blue Glass Arrow RTL  2. L'analisi di complessità degli algoritmiCrystal Clear app kfm home  Algoritmi e programmazioneBlue Glass Arrow  4. Grafi e alberi
Gli appunti che seguono sono contenuti nella sottopagina /sub (modifica · cronologia · aggiorna)
  • 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

  • O\left(n^2\right) (quadratico): semplici, iterativi, basati sul confronto (es. insertion sort, selection sort, bubble sort);
  • O\left(n \sqrt n \right) (es. shell sort);
  • O\left(n \cdot \log{n} \right) (linearitmico): ottimi ma più complessi perché ricorsivi (es. merge sort, quick sort, heap sort);
  • O\left(n\right) (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 confrontoModifica

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

T\left(n\right) = \Omega \left( n \cdot \log{n} \right)
Dimostrazione
Albero delle decisioni

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 2^h foglie per accomodare tutte le n! permutazioni possibili → 2^h \geq n!;
  • tramite la relazione di Stirling n! > {\left( {n \over e} \right)}^n:
    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[1]

Bubble sort (o exchange sort)Modifica

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 sortModifica

Al 1° ciclo, scandisce il vettore, trova la posizione del minimo, e lo scambia con il 1° elemento. Pertanto è il sottovettore sinistro che si riempe 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 sortModifica

È 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

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

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 forT\left(n\right) = O\left( n + k \right): 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: T\left(n\right) = O\left(n\right).

NoteModifica

  1. La base del logaritmo scompare perché si sottointende la moltiplicazione per una costante per il cambio di base.
Blue Glass Arrow RTL  2. L'analisi di complessità degli algoritmiCrystal Clear app kfm home  Algoritmi e programmazioneBlue Glass Arrow  4. Grafi e alberi

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

Inoltre su FANDOM

Wiki casuale