Algoritmi - Programmazione I

Algoritmi Programmazione I

 Algoritmo di ordinamento per inserimento

 Algoritmo di ordinamento per selezione del minimo

 Algoritmo di ordinamento per selezione di massimo

 Algoritmo di fusione

 String Matching

 Algoritmo matching migliore

 Ricorsione in C

 Primo esempio: Fattoriale

 Secondo Esempio: Algoritmo incrementale di somma dei primi numeri

primi n numeri naturali

 Fibonacci

 Algoritmo ricerca binaria, versione iterativa

Versione ricorsiva:

 Complessità di spazio e tempo

 Mappa di memorizzazione

 Algoritmo ricorsivo somma array, approccio incrementale

Approccio divide et impera

Algoritmo di ordinamento per inserimento

- Lo scopo è quello di ordinare in senso crescente un array di

dati.

- Per essere possibile questo ordinamento bisogna che ci sia

una relazione di ordine tra gli elementi dell’array

- Come input abbiamo l’array e il suo size

- Come output abbiamo lo stesso array ma ordinato

- L’AOINS è basato sull’approccio incrementale al problema

dell’ordinamento.

- Infatti ad ogni passo risolve un’istanza del problema, ossia

ordina una porzione per volta di array.

- Ad ogni passo risolve il problema di inserire un elemento

dell’array nella porzione già ordinata alla sua sinistra, in

modo che la lunghezza della porzione ordinata aumenti di 1.

- Il primo elemento è sempre ordinato(nel caso base infatti,

quando abbiamo un array di size 1 è sempre ordinato)

- Quindi il primo passo è ordinare i primi 2 elementi dell’array

- Se l’elemento a sinistra è maggiore allora avviene uno shift a

destra dell’elemento maggiore, altrimenti l’elemento da

inserire viene inserito a destra dell’elemento minore.

- La giusta posizione avviene con un procedimento iterativo a

ritroso (si controllano quindi gli elementi a sinistra e li si

confrontano)

- La struttura è costituita da un ciclo for per i passi e da un

ciclo while innestato per il procedimento a ritroso di

individuazione della giusta posizione.

- L’implementazione è la seguente:

void ord_inser(char array[], int n){

int i, j;

char el_da_ins;

for (i=1; i<n; i++)//gestisce i gli n-1 passi dell’algoritmo

{//lo scopo di i è inserire nella giusta posizione l’elemento di

indice i, salvato in el_da_ins, in modo che da 0 ad i risulti ordinata

el_da_ins = array[i];

j=i-1;

while(j>=0 && el_da_ins < array[j])//processo a ritroso

{

array[j+1] = array[j];

j- -;

}

array[j+1] = el_da_ins; }}//L’uscita dal ciclo while è determinata

dall’aver trovato la giusta posizione e che gli elementi maggiore

di el_da_ins sono stati spostati a destra di tale posizione.

Complessità di spazio:

- N, poiché lavora in “place”

Complessità di tempo:

- Dobbiamo considerare sia gli scambi sia i confronti nel caso

peggiore.

- I confronti sono determinati dall’attivazione del ciclo while,

che viene attivato n-1 volte poiché il while è interno al for. Il

caso peggiore è quando si esce ogni volta da ciclo while

perché j<0, ovvero quando la giusta posizione è sempre la

prima.

- Il caso peggiore è ossia quando l’array e ordinato in senso

decrescente.

- Al primo passo quindi il confronto ne è uno, al secondo 2, al

terzo tre e via dicendo fino ad arrivare ad n-1.

- Per ottenere il numero totale di confronti bisogna sommare i

numeri dei confronti ad ogni passo, cioè(1+2…(n-2)+(n-1))

ma questo non corrisponde altro che alla somma dei primi

numeri naturali che per la formula di Gauss si ha: n*(n-1)/2.

- Per quanto concerne il numero di scambi, o meglio di shift a

destra, basta osservare che si ha uno spostamento ogni volta

che è vero il predicato del while, quindi scambi e confronti

saranno, nel caso peggiore uguali.

- T(n)=n*(n-1)/2= ½(n^2 – n)= O(n^2) confronti/scambi al più

- Il caso migliore è quando l’array è già ordinato, infatti

l’AOINS effettua n-1 confronti e 0 scambi/shift.

- Generalmente si dice che l’AOINS è in grado di accorgersi

con (n-1) confronti del fatto che un array sia già ordinato.

Algoritmo di ordinamento per selezione del minimo

- Lo scopo è ordinare in senso crescente un array di dati

- I dati possono essere numeri, stringhe di caratteri o un

qualsiasi altro insieme che abbia una relazione di ordine.

- L’AOSMIN ha come dati di input un array e il suo size

- E come output ha lo stesso array con i dati ordinati.

- Ad ogni passo(i passi sono n-1 ossia il size meno 1) effettua

la ricerca dell’elemento minimo e la sua posizione, tale

elemento viene scambiato con l’elemento che si trova al

primo posto della porzione che si sta considerando. Al passo

successivo si considera una nuova porzione di array, che

avrà un numero di elementi diminuito di una unità rispetto

alla precedente.

- E si continua così finché non si ha l’array ordinato

- L’implementazione è la seguente:

void ord_sel_min(char array[], int n){

int i;

char min_array;

for(i=0; i<n-1;i++) //gestisce I passi da 0 a n-2

{

min_val_ind(&array[i], n-I, &min_array, &indice_min);

//indice min si riferisce alla porzione dell’array a cui facciamo

riferimento

scambiare_c(&array[i], &array[indice_min+i]);

//Il vero indice globale è indice_min+i

}

}

void min_val_ind(char array[], int n, char *min_array, int

*i_min){

int i;

*min_array = a[0];

*i_min = 0;

for (i=1; i<n; i++)

if (a[i] < *min_array)

{

*min_array = a[i];

*i_min = I;

}

}

void scambiare_c(int *x, int *y){

int temp;

tempo = *x;

*x = *y;

*y = temp;

}

Complessità di spazio:

- N poiché lavora in “place”

Complessità di tempo:

- Consideriamo come operazioni dominanti scambi e confronti

- Entrambi sono determinati rispettivamente gli scambi da

scambiare_c e i confronti da min_val_ind;

- L’attivazione di scambiare_c avviene ad ogni iterazione del

ciclo for ossia da 0 a n-2 elementi(per un totale di n-1

iterazioni)

- Quindi effettua sempre n-1 scambi, è una complessità

assoluta poiché indipendente dal valore degli elementi

dell’array

- I soli confronti sono determinati da min_val_ind, che è

chiamata n-1 volte (una per ogni iterazione del ciclo for)

- Il size della porzione non è costante ma diminuisce di 1

- Alla prima iterazione, la porzione passata alla function

min_val_ind coincide con l’intero array e ha lunghezza n,

quindi la function effettua n-1 confronti. Alla seconda

iterazione , ha la lunghezza diminuita di 1 quindi effettua n-2

confrontti e così via fino ad arrivare a numero di confronti

pari ad 1

- Per ottenere il numero totale di confronti bisogna sommare i

numeri dei confronti ad ogni passo, così abbiamo la somma

dei primi numeri na