Algoritmi di ordinamento - Algoritmi e Strutture Dati

ANALISI DI CORRETTEZZA E DI COMPLESSITÀ DEGLI ALGORITMI

Un algoritmo è una sequenza finita di passi che porta alla soluzione di un problema. Il suo compito è trasformare l'insieme dei dati in ingresso nell'insieme di dati di uscita. Un algoritmo è corretto quando per ogni istanza produce un risultato corretto.

Un algoritmo si inserisce in un programma, infatti quest'ultimo è la traduzione dell'algoritmo in un linguaggio di programmazione.

Vedremo che l'efficienza e la complessità di un algoritmo si misurano tramite il numero di operazioni, che viene espresso in funzione della dimensione del problema che stiamo affrontando.

PROBLEMA ORDINAMENTO

Data una sequenza di n valori di ingresso {a1, a2, ..., an} determinare una permutazione {a1', a2', ..., an'} della sequenza di ingresso tale che a1' ≤ a2' ≤ ... ≤ an'.

Il primo algoritmo che vediamo come soluzione a tale problema è il seguente:

INSERTION SORT

Si tratta di un algoritmo che ordina sul posto, cioè ordina i valori all'interno dell'array stesso, con al più un numero costante di valori memorizzati al di fuori dell'array in ogni momento. Tale algoritmo procede considerando un valore alla volta e inserendolo nella corretta posizione tra i valori che lo precedono. Per fare ciò l'algoritmo opera su una sotto-vettore del vettore di partenza e considera di volta in volta come primo elemento che (posto base) risulta essere di per sé ordinato, considera poi soltanto due elementi, e l'ordine, sostituendo tale sottosequenza ordinata all'interno del vettore, e così via.

Supponiamo di voler inserire eg nella posizione j+1, sapendo che primi j+1 elementi sono ordinati. Come inseriamo j in modo da ottenere una sequenza ordinata?

Per prima cosa salvo ej in una locazione di memoria, poi confronto ej con tutti gli elementi. Inizia a partire da (j-1) e (j-1)=m: Si possono incontrare due casi:

• ej ≥ ej-1: allora lascia ej nella posizione in cui si trova e termina l'iterazione
• ej < ej-1: allora faccio scorrere ej-1 verso destra, spingendolo nella posizione j+1 e passo a confrontare ej con ej-2, j+1

Iterando tale procedimento troverò la posizione corretta in cui inserire ej.

ESEMPIO:

1. 5 2 4 6 1 3
2. 6 2 4 6 1 3
3. 2 5 4 6 1 3
4. 2 5 4 6 4 3
5. 2 4 5 6 4 3

Il primo elemento è già ordinato.

Salvo 2 in una locazione di memoria e poi lo confronto con 5. Poiché 2 ≤ 5, sposto 5 verso destra e metto 2 nella prima posizione.

Salvo 4 in una locazione di memoria e poi lo confronto con 5. Poiché 4 ≤ 5, posto 5 verso destra. Confronto poi 4 con 2 ed essendo 2 ≤ 4, memorizzo 4 nella posizione due.

E così via.

Oss: Ordinare sul posto significa non richiedere ulteriore memoria. L'algoritmo usa una quantità di memoria costante per effettuare le proprie operazioni.

Insertion-Sort (A)

for j ← 2 to length[A] do

• usi il ciclo for perchè si deve eseguire un numero di iterazioni pari a (length[A]-1)
• viene copiato l'elemento A[j] nella locazione temporanea di memoria

key ← A[j]

i ← j-1

while i > 0 and A[i] > key do

• usi il ciclo while perchè potrebbe succedere che non venga mai eseguito
• le condizioni di terminazione del ciclo sono: A[i] ≤ A[j], oppure valore finito (i=0)
• Restiamo nel ciclo invece se: A[i+1] = A[i] e i ≥ 0

do A[i+1] ← A[i]

i ← i-1

A[i+1] ← key

• tale assegnazione alla fine deve essere fatta sia se usciamo perchè i < 0, sia se usciamo perché A[i] ≤ key

Oss.1

Le strutture iterative sono:

• for: quando conosciamo già il numero di iterazioni da eseguire
• while e do-while: quando non conosciamo il numero di iterazioni, ma la fine del ciclo dipende dal verificarsi di una o più condizioni. Nel caso del do-while il ciclo viene eseguito almeno una volta; nel caso del while potrebbe non essere eseguito mai.

Oss.2

Nel ciclo for usiamo un contatore che parte dall'indice del secondo elemento del vettore e arriva alla lunghezza di A. Questo perchè in stile for ogni pseudo-codice gli indici dei vettori partono da 1 (e non da 0 come maggiori siamo abituati in C).

Oss.3

Nel ciclo while è importante l'ordine delle condizioni di continuazione (cioè i > 0) deve stare prima di A[i] > key, perchè altrimenti nell'ultima iterazione confronterei A[0] > key in A[0] non c'è elemento del vettore e questo potrebbe portare ad un segmentation fault, quando si passai al codice reale. Per tutti quegli algoritmi che faremo assumiamo che venga sempre fatta la valutazione di corto circuito. Da alcuni compilatori, se trovano la prima condizione falsa, allora non verificano proprio la seconda condizione poiché c'è un operatore di congiunzione AND.

Correttezza

Tale algoritmo è iterativo allora la correttezza si dimostra tramite l'invariante del ciclo. Si tratta di una proprietà che deve essere vera prima dell'inizio del ciclo, e se vera prima dell'inizio di un'iterazione, allora deve essere vera anche dopo. In fine tale proprietà deve essere vera anche alla fine del ciclo.

Per prima cosa dobbiamo trovare l'invariante del ciclo for: tutti gli elementi di A da A o J sono ordinati e corrispondono agli elementi che precedentemente si trovavano in quella sequenza (l'ordine eventualmente diverso).

• All'inizio del ciclo, quando j=2, nella posizione A si trova un unico elemento che quindi risulta essere ordinato ed era già presente nel vettore.
• consideriamo l'iterazione che porta dal passo J-1: supposto che l'invariante sia vero per j-1, allora si consideriamo l'iterazione successiva che parte da J e posiamo dire che sicuramente (il sequenza che va dall'elemento A[1] a A[j-1] ordinata e composta da element che si trovavano originariamente nel vettore di partenza;
• il ciclo termina quando j=n+1, ovvero quando la sequenza da A[1] a A[n] è ordinata e quindi l'invariante è soddisfatto.

i ← j ← 1

for k ← p to r

• do if L[i] ≤ R[j]
• then A[k] ← L[i]
• i ← i + 1
• else A[k] ← R[j]
• j ← j + 1

Il valore sentinella può essere codificato con il massimo valore rappresentabile relativamente al tipo che si sta utilizzando (in C++ c'è la classe numeric_limits).

Merge-Sort(A,p,r)

• è un algoritmo ricorsivo

if p < r

• then q ← ⌊(p+r)/2⌋
• calcolo il punto medio del vettore

Merge-Sort(A,p,q)

Merge-Sort(A,q+1,r)

Merge(A,p,q,r)

• combino le due soluzioni ottenute prima

Os. I sottoproblemi sono relativi a sottovettori che non si intersecano

CORRETTEZZA

l'invariante del ciclo è il seguente:

• All'inizio di ciascuna iterazione dell'ultimo ciclo for, la sottosequenza A[p..k-1] contiene k-p elementi ordinati più piccoli degli elementi di L e R. Inoltre le due teste L[i] e R[j] sono i più piccoli elementi dei loro array a non essere stati ancora ricopiati in A.

A questo punto facciamo vedere che:

• l'invariante è vero prima della prima iterazione
• Per k = p, la sottosequenza A[p..k-1] è vuota (k=p). Inoltre L[i] e R[j] sono i più piccoli elementi dei loro array a non essere stati ricopiati in A.
• un'iterazione del ciclo conserva la verità dell'invariante
• ad ogni iterazione A[p..k] contiene k-p elementi più piccoli di L e R ordinati; inoltre L[i] e R[j] sono i più piccoli elementi di L e R a non essere stati ricopiati in A.
• se L[i] <= R[j] allora L[i] viene ricopiato in A[k] e i costⁱ la verità di A[p..k+1].
• considera k-p+1 elementi più piccoli di L e R ordinati. Incrementando k ed i, si stabilisce l'invariante per la successiva iterazione.