03: Ordinamento

Il problema di ordinamento (sorting) consiste nel riorganizzare gli elementi di un vettore in modo tale che siano disposti in ordine crescente (o decrescente).

La ricerca binaria (ricerca dicotomica) è un algoritmo che trova un elemento specifico in un vettore ordinato in tempo logaritmico. Dividendo il vettore a metà ad ogni passo, cerca l'elemento nel sottovettore corretto.

Insertion sort è un algoritmo di ordinamento che inserisce ogni elemento, a partire dal secondo, nella posizione corretta nella parte già ordinata del vettore.

Selection sort è un algoritmo di ordinamento che cerca il minimo elemento nel vettore e lo scambia con l'elemento in prima posizione. Poi ripete questa operazione per il resto del vettore, trovando il minimo tra gli elementi rimanenti.

Il caso peggiore è una situazione in cui un algoritmo richiede il maggior tempo di esecuzione. Per la ricerca in un vettore non ordinato, il caso peggiore si verifica quando l'elemento cercato si trova nell'ultima posizione.

Una permutazione di un vettore è una riorganizzazione dei suoi elementi in un ordine diverso.

L'analisi della complessità di un algoritmo studia il numero di operazioni eseguite dall'algoritmo al crescere della dimensione dell'input.

Un invariante è una condizione che rimane vera durante l'esecuzione di ogni fase di un algoritmo. L'invariante di insertion sort afferma che la parte sinistra del vettore è sempre ordinata.

Il numero di volte che la riga 3 del codice viene eseguita per un dato valore di i.

Il caso peggiore per l'algoritmo di ordinamento che comporta il maggior numero di scambi e, quindi, un tempo di esecuzione più lungo.

L'esecuzione del codice comporta un'iterazione del ciclo esterno (riga 2) e un numero di iterazioni del ciclo interno (riga 3) che varia a seconda del valore di i.

L'espressione matematica per calcolare il tempo di esecuzione dell'algoritmo nel caso peggiore.

Il tempo di esecuzione dell'algoritmo nel caso peggiore è proporzionale al quadrato del numero di elementi del vettore.

La riga 4 viene eseguita ti-1 volte per un dato valore di i, ovvero una volta in meno rispetto alla riga 3.

Il tempo di esecuzione dell'algoritmo è proporzionale al quadrato del numero di elementi del vettore per valori grandi di n.

L'algoritmo ha una complessità temporale quadratica, ovvero il tempo di esecuzione cresce in modo quadratico con la dimensione dell'input N.

L'invariante di un ciclo è una condizione che è vera all'inizio del ciclo e che rimane vera dopo ogni iterazione del ciclo.

L'invariante del ciclo esterno dell'Insertion Sort è che il sottovettore A[1..i-1] è ordinato.

L'invariante del ciclo interno dell'Insertion Sort è che i vettori A[1..j-1] e A[j..i] sono ordinati e che ogni elemento in A[1..j-1] è minore o uguale a qualsiasi elemento in A[j+1..i].

L'inizializzazione dell'invariante del ciclo esterno avviene quando i = 2, quindi il sottovettore A[1..i-1] contiene solo il primo elemento e, quindi, è ordinato.

Il mantenimento dell'invariante del ciclo esterno avviene quando il ciclo interno inserisce correttamente A[i] nella sua posizione, mantenendo ordinato il sottovettore A[1..i-1].

L'uscita dell'invariante del ciclo esterno avviene quando i = n+1, quindi l'invariante implica che l'intero vettore è ordinato.

L'inizializzazione dell'invariante del ciclo interno avviene quando j = i, quindi il sottovettore A[1..j-1] è vuoto e il sottovettore A[j..i] contiene un solo elemento. L'invariante è vero perché un vettore di un elemento è ordinato e non c'è nessun elemento in A[j+1..i].

Il mantenimento dell'invariante del ciclo interno avviene in due modi: 1. Se A[j-1] è minore o uguale a A[j] (o j = 1), il ciclo interno termina e l'invariante è vero perché il sottovettore A[1..i] è ordinato. 2. Se A[j-1] è maggiore di A[j], viene fatto uno scambio tra A[j-1] e A[j]. L'invariante rimane vero perché lo scambio mantiene ordinato il sottovettore A[1..j-1] e continua ad essere vero per il sottovettore A[j..i].

Nel caso migliore, il tempo di esecuzione di un algoritmo è proporzionale alla dimensione dell'input. Ad esempio, se l'input è un vettore di 'n' elementi, il tempo di esecuzione è proporzionale a 'n'.

Il tempo di esecuzione di un algoritmo nel caso migliore può essere espresso come una funzione lineare della dimensione dell'input 'n'. Questo significa che il tempo di esecuzione aumenta linearmente con 'n'.

L'invariante di Selection sort assicura che, ad ogni passo, la parte ordinata del vettore contiene i 'i-1' elementi più piccoli del vettore originale, mentre la parte non ordinata contiene gli elementi rimanenti.

Il ciclo interno di Selection sort trova l'indice 'k' dell'elemento minimo nella parte non ordinata del vettore.

Il ciclo esterno di Selection sort itera su ogni elemento del vettore, a partire dal primo.

Dopo aver trovato l'indice 'k' dell'elemento minimo, la riga 8 di Selection sort scambia l'elemento in posizione 'i' con l'elemento in posizione 'k'.

La dimostrazione della correttezza di Selection sort si basa sull'invariante del ciclo. L'invariante garantisce che la parte ordinata del vettore sia sempre ordinata correttamente e che contenga gli elementi più piccoli del vettore originale.

Nell'algoritmo Selection Sort, l'invariante del ciclo interno afferma che l'elemento A[k] è il minimo tra gli elementi del sottovettore A[i..j-1].

L'invariante del ciclo interno viene inizializzato impostando k=i e j=i+1, il che è banale poiché il minimo tra un solo elemento è l'elemento stesso.

Nell'algoritmo Selection Sort, l'ipotesi induttiva è che l'invariante sia vero prima di eseguire il corpo del ciclo interno. Dopo aver confrontato A[k] con A[j], si aggiorna k se A[j] è più piccolo. Quindi j viene incrementato, mantenendo vera la condizione di minimo.

Quando il loop interno termina (j = n+1), l'invariante implica che A[k] è il minimo in A[i..n], dimostrando che l'algoritmo funziona correttamente.

La complessità temporale del Selection Sort, nel caso peggiore, è di O(n^2).

Nel caso peggiore, l'indice del minimo in A[i..n] viene aggiornato ad ogni iterazione del ciclo interno.

Il numero di operazioni eseguite da ciascuna riga del codice Selection Sort è considerato costante e pari ad 1.

La complessità temporale del Selection Sort è un polinomio di secondo grado in n, quindi possiamo dire che è O(n^2).