Fondamenti di Informatica CDL in Ingegneria Meccanica (B) - A.A. 2009-2010 CDL in Ingegneria...

Fondamenti di Informatica Fondamenti di Informatica

CDL in Ingegneria Meccanica (B) - A.A. 2009-2010CDL in Ingegneria Meccanica (B) - A.A. 2009-2010

8. Problemi ricorrenti: 8. Problemi ricorrenti: ordinamento e ricercaordinamento e ricerca

Ing. Ing. Simona ColucciSimona Colucci

Sistemi Sistemi InformativiInformativiDEE - Politecnico di BariDEE - Politecnico di Bari

Fondamenti di Informatica Fondamenti di Informatica CDL in Ingegneria Meccanica (B) - A.A. 2009-2010CDL in Ingegneria Meccanica (B) - A.A. 2009-2010

IndiceIndice

• Problemi ricorrenti in informatica:– Ordinamento di un vettore:

• Ordinamento per selezione:– il metodo di selezione diretta (selection sort)

• Ordinamento per scambio: – il metodo dell’affioramento(bubble sort)– Il metodo dell’ordinamento non decrescente(quick sort)

• Ordinamento per fusione (merge-sort)

– Ricerca in un vettore:• Ricerca sequenziale• Ricerca dicotomica



Il problema dell’ordinamentoIl problema dell’ordinamento

• Il problema è quello di ordinare gli elementi di un insieme secondo una prefissata relazione d’ordine, che dipende dalla natura dei dati da ordinare

• I metodi di ordinamento si applicano ad – insiemi di dati elementari (singoli numeri o lettere) – dati rappresentati in forma complessa: in generale si fa

riferimento ad un insieme di record, dei quali si seleziona un campo che viene usato come campo chiave per l’ordinamento; il risultato dell’ordinamento sarà una ridisposizione dei record secondo l’ordinamento introdotto nel campo considerato.



Metodi di ordinamentoMetodi di ordinamento

Classificazione:• Inserzione: Si considerano gli elementi uno alla volta e ciascun

nuovo elemento viene collocato nella posizione che gli compete all’interno dell’insieme di elementi considerati in precedenza.

• Selezione: Si scandisce l’insieme in modo da individuare l’elemento più piccolo, che viene separato dal resto dell’insieme. Dell’insieme rimasto viene ancora trovato il più piccolo elemento e lo si colloca di seguito a quello trovato in precedenza. Questo procedimento si itera fino a quando non si sono considerati tutti gli elementi.

• Scambio: Si scandisce tutto l’insieme, se due elementi vengono trovati fuori posto si scambiano tra loro. Questo procedimento viene ripetuto fino a quando non si hanno più cambiamenti.

• Fusione: Si sfrutta un’operazione più semplice dell’ordinamento, chiamata fusione, che consiste nel formare un insieme ordinato a partire da due insiemi già ordinati



Prestazioni degli algoritmiPrestazioni degli algoritmi

• Misurate tramite due fattori:– Numero di confronti necessari per determinare gli

elementi fuori posto– Numero di spostamenti da effettuare per riportare gli

elementi al loro posto

• Algoritmi con valore basso per i due fattori sopra esposti sono più efficienti: eseguono l’ordinamento in meno passaggi, cioè impiegando meno tempo e spazio



Ipotesi di lavoroIpotesi di lavoro

Nel seguito:• come insieme di dati da ordinare considereremo un vettore

di numeri interi V di dimensione N; V[i] indicherà l’i-esimo elemento del vettore.

• La relazione d’ordine che si prenderà in considerazione è l’usuale ordinamento numerico (basato sui concetti di minore e maggiore)

• Supporremo di realizzare un ordinamento crescente.• Con l’istruzione V[i] V[k] abbrevieremo il seguente

blocco di istruzioni di scambio:– lavoro = V[i];– V[i] = V[k];– V[k]= lavoro;



Ordinamento per selezione Ordinamento per selezione

Selection Sort : Il metodo di selezione diretta:

• Il metodo fa uso di due indici di posizione :– i: è l’indice dell’elemento del vettore che delimita l’inizio

dell’insieme dei valori presi in considerazione ad ogni singolo passo

– j: è un cursore che ad ogni passo percorre l’insieme dei valori da scandire

– k: è un indice che all’interno di ogni passo tiene traccia del minimo progressivo dell’insieme da scandire



Ordinamento per selezioneOrdinamento per selezione

Algoritmo di selezione diretta:• Passo 0:

– All’inizio l’indice i viene posizionato sul primo elemento del vettore V; j invece comincia a scandire dal secondo elemento

• Passo 1:– Il primo elemento viene confrontato con i rimanenti (scanditi

da j), scambiando di posto il primo elemento e quello di valore minimo alla fine della scansione(posizione k)

• Passo 2:– Al secondo passo l’indice i viene portato alla seconda

posizione, perché il nuovo insieme dei valori da scandire non comprende il primo, che è sicuramente il minimo

• Passi successivi:– L’indice j percorre l’insieme dei valori da scandire, a partire

dall’elemento successivo a i; il processo riprende in maniera analoga al passo precedente e viene iterato finché l’indice i non giunge all’ultima posizione.



EsempioEsempio

• le colonne rappresentano i passi dell’algoritmo• gli elementi evidenziati in azzurro rappresentano il

sottoinsieme del vettore da scandire per l’ordinamento ad ogni passo

• il cerchio rosso rappresenta l’elemento minimo di ognuno dei sottoinsiemi

25 8 8 8 8

37 37 25 25 25

41 41 41 27 27

27 27 27 41 37

8 25 37 37 41



Prestazioni dell’algoritmoPrestazioni dell’algoritmo

• Il metodo di selezione diretta presenta un numero di confronti proporzionale ad N2:– al primo passaggio si effettuano N-1 confronti, al secondo

N-2 e così via, fino ad arrivare all’ultimo confronto; si ha pertanto:

(N-1) + (N-2) + (N-3) + ….. +1 = N(N-1)/2• Per quanto riguarda il numero di spostamenti essi

sono al più N-1.• La prestazione del metodo per quanto riguarda il

numero di confronti non è influenzata dalla configurazione iniziale dei dati(se sono ordinati o meno)



Selezione diretta: flow-chartSelezione diretta: flow-chart

inizio

i =0

j = i+1

V[k]>= V[j]

V[i] V[k]

j++

j<N

i<N-1

i++

k = j

k != i

k = i

vero

falso

vero

verofalso

vero

fine

falso

• Le istruzioni di scambio si trovano nel ciclo scandito dalla i, per cui vengono eseguite N-1 volte AL PIU’ (solo se K!=i)

•I confronti vengono effettuati N-1 volte per ognuno degli N cicli scanditi dalla i, perché si trovano in un’istruzione di controllo all’interno dei due cicli

falso



Codice SorgenteCodice Sorgente

#include <stdio.h>

#define N 10

void main()

{int i, k, j;

int V[N];

int temp;

for(i=0; i<N; i++)

{printf("Inserisci un numero\n");

scanf ("%d", &V[i]);

}

i=0;

do{ k=i; for(j=i+1; j<N; j++ ) if(V[j]<= V[k]) k=j; if(k!=i) {temp = V[i]; V[i]=V[k]; V[k]=temp; } i++; }while(i<N-1);

for(i=0; i<N; i++) printf("%d\n", V[i]); getch(); }



Il problema della ricercaIl problema della ricerca

• Il problema è quello di cercare un elemento in un vettore

• I metodi di ricerca si applicano ad – insiemi di dati elementari (singoli numeri o lettere) – dati rappresentati in forma complessa: in generale si fa

riferimento ad un insieme di record, dei quali si cercano uno o più campi che vengono usati come campi chiave per la ricerca.



Metodi di ricercaMetodi di ricerca

• Metodi basati sul confronto di chiavi: si confrontano gli elementi del vettore con l’elemento (chiave) che si vuole ricercare:– Ricerca lineare: si confronta ripetutamente la chiave

con ciascuno degli elementi del vettore finché eventualmente non si trova la chiave

– Ricerca dicotomica: Si confronta la chiave con l’elemento che si trova a metà del vettore (supposto ordinato). Se l’elemento individuato non è uguale a quello cercato si prosegue la ricerca nel semivettore inferiore o superiore a seconda che la chiave sia più piccola o più grande dell’elemento che si trova a metà.



Ipotesi di lavoroIpotesi di lavoro

• Elementi utilizzati nell’analisi:– Vettore V di dimensione N– Chiave di ricerca K– Indice i per scorrere il vettore– t = indice che punta all’inizio del vettore in cui ricercare– u= indice che punta alla fine del vettore in cui ricercare



Ricerca lineareRicerca lineare

• Principio risolutivo:Si confronta ripetutamente la chiave K con ciascuno degli elementi del vettore finché non si trova V(i) = K (ricerca con successo) oppure finché non sono stati considerati tutti gli elementi del vettore senza trovarne nessuno uguale a K (ricerca senza successo).



Ricerca lineare: flow-chart Ricerca lineare: flow-chart

start

i = -1

i = i+1

K ≠ V [i]and

i < Nsi

no

i <Nsino

Elementotrovato

ElementoNon trovato

end



RICERCA LINEARE: Numero ConfrontiRICERCA LINEARE: Numero Confronti

Due valutazioni diverse a seconda dell’esito della ricerca:• ricerca con successo:si fa riferimento al numero medio di confronti, che si ottiene dividendo il numero totale di confronti necessari per ricercare tutti gli elementi per il numero degli elementi stessi. Siccome per individuare il primo elemento si effettua un confronto, per il secondo due e così via, il numero totale di confronti è :

1+2+3+4+5+….. N = N(N+1)/2Il numero medio di confronti risulta (N+1)/2• ricerca senza successo:l’algoritmo esamina sempre tutto il vettore, quindi il numero di confronti è sempre N



Ricerca in vettori ordinatiRicerca in vettori ordinati

Vantaggio:Il numero di confronti in caso di ricerca senza successo è lo stesso che nella ricerca con successo (N+1)/2, perché si procede alla scansione del vettore finché K ≤ V[i]. A questo punto o K= V[i], e la ricerca è con successo, oppure si possono interrompere i confronti, e la ricerca risulta senza successo. Pertanto si determina il numero medio di confronti come in caso di successo



RICERCARICERCA BINARIA BINARIA (detta dicotomica o logaritmica) (detta dicotomica o logaritmica)

• Si applica su vettori ordinati• Si confronta la chiave K con l’elemento che si trova a metà del

vettore. Se l’elemento individuato non è uguale a quello cercato si prosegue la ricerca nel semivettore inferiore o superiore a seconda che la chiave K sia più piccola o più grande dell’elemento che si trova a metà.

• Il procedimento continua iterativamente in modo da suddividere le sottotabelle via via individuate.

• La ricerca termina con successo quando l’elemento V[i] considerato ad un certo passo è proprio uguale a K.

• La ricerca termina con insuccesso quando la parte di vettore considerata è costituita da un solo elemento.



Ricerca dicotomica: flow-chartRicerca dicotomica: flow-chart

start

t = 0

u = N-1

K ≠ V [i]

i = (t+u)/2

K > V [i]

t = i + 1u = i - 1

si

si no

t <= u and K ≠ V [i]

ElementoNon trovato

Elementotrovato

end

sino

no

si

no

K ≠ V [i]



Ricerca dicotomica: codice (1/2)Ricerca dicotomica: codice (1/2)

Versione iterativa

//Ricerca dicotomica di una chiave K in un vettore V

#include <stdio.h>#define N 10main(){ int i, t, u, K;

printf(“Digitare la chiave di ricerca”); scanf(“%d”, &K); i=0; t=0; u=N-1; do { i=(u+t)/2; if (K!=V[i]) { if (K>=V[i]) t=i+1; else u=i-1;} } while((t<=u) && (K!=V[i]));

if (K!=V[i]) printf("Elemento non trovato nel vettore alla posizione %d", i+1); else printf("Elemento trovato nel vettore"); }



Ricerca dicotomica: codice (2/2)Ricerca dicotomica: codice (2/2)

Versione ricorsiva

//Ricerca dicotomica di un brano(key) in un elenco di //titoli(ptot) con estremi t ed u

void ricercabin(char key[30], brano ptot[200], int t, int u){ int i; i=(u+t)/2; if ((t<=u) && (strcmp(key, ptot[i].titolo)!= 0)) { if ((strcmp(key, ptot[i].titolo) > 0)) t=i+1; else u=i-1; ricercabin(key, ptot, t, u); } else if ((strcmp(key, ptot[i].titolo)== 0) ) printf("Elemento trovato nel vettore alla posizione %d", i+1); else printf("Elemento non trovato nel vettore"); }



RICERCA DICOTOMICA:RICERCA DICOTOMICA: Numero Confronti Numero Confronti

• L’algoritmo è il più veloce tra quelli di ricerca basati sul confronto di chiavi.• In un vettore di dimensione

N = 2h -1 l’algoritmo deve compiere

h=log2(N+1) passi(e quindi confronti) per la ricerca senza successo, mentre i confronti possono essere di meno per la ricerca con successo.

Fondamenti di Informatica Fondamenti di Informatica

CDL in Ingegneria Meccanica (B) - A.A. 2009-2010CDL in Ingegneria Meccanica (B) - A.A. 2009-2010

Solo per approfondimentoSolo per approfondimento::Ordinamento con algoritmi Ordinamento con algoritmi

bubble sort, quicksort e mergesort bubble sort, quicksort e mergesort



Ordinamento per scambio Ordinamento per scambio

Il procedimento tipico di qualsiasi algoritmo di scambio è il seguente:

• si considerano i primi due elementi dell’insieme; se il primo elemento della coppia è maggiore del secondo i due elementi vengono scambiati di posto tra di loro;

• si considera ora una nuova coppia formata dal secondo e dal terzo elemento dell’insieme, si confrontano e si scambiano le posizioni se necessario;

• questo procedimento si ripete, considerando coppie di elementi consecutivi, fino a quando non si è esaurito tutto l’insieme



Ordinamento per scambioOrdinamento per scambio

Il metodo dell’affioramento (Bubble Sort)• Gli elementi più “pesanti” tendono ad andare

verso il basso e quelli più leggeri verso l’alto:– ad ogni passo (step) dell’algoritmo l’elemento in

assoluto più pesante sarà collocato nella posizione finale, che al passo successivo non verrà più scandita

• Il numero massimo di passi è N-1 , ma dato che ad ogni passo più elementi potrebbero essere “a posto”, i passi potrebbero anche di meno



EsempioEsempio

• le colonne rappresentano i passi dell’algoritmo• gli elementi evidenziati in azzurro rappresentano il

sottoinsieme del vettore da scandire per l’ordinamento ad ogni passo

• il cerchio rosso rappresenta l’elemento massimo di ognuno dei sottoinsiemi

25 25 25 25 8

37 37 27 8 25

41 27 8 27 27

27 8 37 41 37

8 41 41 37 41



Bubble Sort: Flow-chartBubble Sort: Flow-chart

• La variabile più importante usata nel procedimento è:– scambi: viene inizializzata a

0 ad ogni passo e serve per controllare se ci sono stati scambi ad un certo passo: se non ce ne sono il resto di vettore è ordinato

j = j + 1

j < N - step

V[j] V[j+1] scambi = 1

inizio

fine

step = 1

j = 0

step = step + 1

step < N && scambi = 1vero

falso

vero

falso

vero

falso

V[j]>V[j+1]

scambi = 0



Codice SorgenteCodice Sorgente

#include <stdio.h>#define N 10void main(){int j, step, scambi;int V[N];int temp;

for(j=0; j<N; j++) {printf("Inserisci un numero\n"); scanf ("%d", &V[j]); }

step=1 ;do{ scambi=0 ; for(j=0; j< N-step; j++ ) if(V[j+1]< V[j]) {scambi =1; temp = V[j+1]; V[j+1]=V[j]; V[j]=temp; } step++; }while(step<N && scambi !=0);

for(j=0; j<N; j++) printf("\n%d", V[j]); getch(); }



PrestazioniPrestazioni

• Numero di confronti: – l’analisi del caso peggiore porta a concludere che il metodo è di

ordine N2 ; il caso peggiore si ha quando l’insieme è ordinato in modo decrescente e da vita ad un numero complessivo di confronti pari a

(N-1) + (N-2) + (N-3) + ….. +1 = N(N-1)/2– Si può dimostrare che questa valutazione è vera anche nella media

dei casi– Nel caso in cui in qualche passo vada a posto più di un elemento il

numero di confronti complessivi da operare sarà inferiore• Numero di spostamenti:

– Si segue un ragionamento analogo (nel caso peggiore sono N(N-1)/2).

La prestazione del metodo è pertanto influenzata dalla configurazione iniziale dei dati



Quicksort Quicksort

• Considerato un elemento a caso, che chiamiamo perno o separatore, si effettua una partizione dell’insieme collocando nella sua giusta posizione il perno e allocando alla sua sinistra tutti gli elementi più piccoli ed alla sua destra tutti gli elementi più grandi del perno stesso

• Sui due sottoinsiemi disordinati così individuati si applica ricorsivamente il concetto di partizione



Quicksort: strategiaQuicksort: strategia

• Concetto base:

• Una sola scansione del vettore è sufficiente per collocare definitivamente un elemento (per esempio il primo) nella sua destinazione finale e allo stesso tempo per lasciare tutti gli elementi con un valore inferiore a quello da una parte, anche se disordinati, e tutti quelli con un valore maggiore, dall'altra

• In questo modo, attraverso delle chiamate ricorsive, è possibile elaborare i due segmenti del vettore rimasti da riordinare.



Quicksort: algoritmo approssimatoQuicksort: algoritmo approssimato

• L'algoritmo può essere descritto grossolanamente come: – localizzazione della collocazione finale del primo valore,

separando in questo modo i valori(procedura di partizione); – ordinamento del segmento precedente all'elemento collocato

definitivamente; – ordinamento del segmento successivo all'elemento collocato

definitivamente.

• Variabili impiegate:– LISTA : il vettore da ordinare in modo crescente. – A: l'indice inferiore del segmento di vettore da ordinare. – Z: l'indice superiore del segmento di vettore da ordinare. – CF : sta per «collocazione finale» ed è l'indice che cerca e

trova la posizione giusta di LISTA[A] nel vettore. – I: è l'indice che insieme a CF serve a ripartire il vettore.



Procedura di partizione:PARTProcedura di partizione:PART

• Sia LISTA il vettore da ordinare• Il primo elemento da collocare corrisponde inizialmente a

LISTA[A], e il segmento di vettore su cui intervenire corrisponde a LISTA[A:Z] (cioè a tutti gli elementi che vanno dall'indice A all'indice Z)

• Alla fine della prima scansione, l'indice CF rappresenta la posizione in cui occorre spostare il primo elemento, cioè LISTA[A]. In pratica, LISTA[A] e LISTA[CF] vengono scambiati.

• Alla fine della prima scansione, gli elementi contenuti in LISTA[A:(CF-1)] devono contenere valori inferiori o uguali a LISTA[CF], mentre quelli contenuti in LISTA[(CF+1):Z] devono contenere valori superiori.



Quicksort: QSORTQuicksort: QSORT

• Indichiamo con QSORT la procedura che esegue il compito complessivo di ordinare il vettore. Il suo lavoro consisterebbe nel chiamare PART per riordinare gli elementi che vanno dal primo all'ultimo del vettore LISTA restituendo l'indice della collocazione finale, e quindi di richiamare se stessa in modo da riordinare la prima parte e poi la seconda.

• Se l'indice Z non è maggiore di A, allora c'è un elemento (o nessuno) all'interno di LISTA[A:Z] e LISTA[A:Z] è già nel suo stato finale.

• Se Z è maggiore di A, allora PART ripartisce correttamente LISTA[A:Z]. L'ordinamento separato dei due segmenti completa l'ordinamento di LISTA[A:Z]



PART: fasi della scansionePART: fasi della scansione

• La scansione del vettore da parte di PART avviene portando in avanti l'indice I e portando indietro l'indice CF. Quando l'indice I localizza un elemento che contiene un valore maggiore di LISTA[A], e l'indice CF localizza un elemento che contiene un valore inferiore o uguale a LISTA[A], gli elementi cui questi indici fanno riferimento vengono scambiati, quindi il processo di avvicinamento tra I e CF continua



• Quando la scansione è giunta al termine, quello che resta da fare è scambiare l'elemento LISTA[A] con LISTA[CF]

PART: fasi della scansionePART: fasi della scansione



PART: la scansione in praticaPART: la scansione in pratica

• L'indice I, iniziando dal valore A+1, viene spostato verso destra fino a che viene trovato un elemento maggiore di LISTA[A] quindi è l'indice CF a essere spostato verso sinistra, iniziando dalla stessa posizione di Z, fino a che viene incontrato un elemento minore o uguale a LISTA[A]. Questi elementi vengono scambiati e lo spostamento di I e CF riprende

• Si prosegue fino a che I e CF si incontrano, e in quel momento LISTA[A:Z] è stata ripartita, e CF rappresenta la collocazione finale per l'elemento LISTA[A]



PART: flow-chartPART: flow-chart



Quicksort: algoritmo dettagliatoQuicksort: algoritmo dettagliato

• L’algoritmo di quicksort può essere schematicamente definito come: – se A= Z stop– esegui l’algoritmo di partizione su LISTA delimitato da A

e Z determinando la posizione CF dell’elemento separatore

– Se A < CF esegui quicksort su LISTA delimitato da A, CF-1

– Se CF < Z esegui quicksort su LISTA delimitato da CF+1, Z



Codice Sorgente(1/2)Codice Sorgente(1/2)

#include <stdio.h>#define N 10

void quicksort( int V[ ], int A, int Z);int part( int V[ ], int A, int Z);

main(){int j; int V[N];

for(j=0; j<N; j++) {printf("Inserisci un numero\n"); scanf ("%d", &V[j]); }quicksort(V, 0, N);for(j=0; j<N; j++) printf("\n%d", V[j]); getch();}

void quicksort( int Vett[ ], int A, int Z){int ris;if (A!=Z) { ris= part(Vett, A, Z); if (ris>A) quicksort(Vett, A, ris-1); if (ris<Z) quicksort(Vett, ris+1, Z); }

}



Codice Sorgente(2/2)Codice Sorgente(2/2)

int part(int LISTA[ ], int A, int Z){int I, CF; int temp; I=A; CF=Z; while(I<CF) {do{CF--;} while (LISTA[CF]>LISTA[A]); do{I++;} while (LISTA[I]< LISTA[A] && I<CF); if(I<CF) {temp = LISTA[CF]; LISTA[CF]=LISTA[I]; LISTA[I]=temp;} }temp = LISTA[CF];LISTA[CF]=LISTA[A];LISTA[A]=temp;return CF;}



Quicksort: esempio di Quicksort: esempio di applicazioneapplicazione

LISTA (34 93 64 25 18 29 76 81), di 8 elementi delimitato da A = 1 e Z = 8.

1. siccome A=Z è falso si va in sequenza;2. si esegue partizione su LISTA delimitato da A=1 e Z=8 trovando la

posizione CF = 4 per il separatore 34. 3. poiché A < CF è vero si esegue quicksort su LISTA delimitato da A=1 e Z=

3 3.1 siccome A=Z è falso si va in sequenza; 3.2 si esegue partizione su LISTA delimitato da A=1 e Z=3 trovando la

posizione CF = 3 per il separatore 29. 3.3 poiché A < CF è vero si esegue quicksort su LISTA delimitato da A=1

e Z= 2 3.3.1 siccome A=Z è falso si va in sequenza; 3.3.2 si esegue partizione su LISTA delimitato da A=1 e Z=2

trovando la posizione CF=2 per il separatore 25. 3.3.3 poiché A < CF è vero si esegue quicksort su LISTA delimitato da A=1 e Z= 1

3.3.3.1 siccome A=Z è vero si rientra 3.3.4 Poiché CF< Z è falso, si rientra

3.4 Poiché CF< Z è falso, si rientra



Quicksort: esempio di Quicksort: esempio di applicazioneapplicazione

4. poiché CF < Z è vero si esegue quicksort su LISTA delimitato da A=5 e Z= 8 4.1 siccome A=Z è falso si va in sequenza; 4.2 si esegue partizione su LISTA delimitato da A=5 e Z=8 trovando la

posizione CF = 5 per il separatore 64. 4.3 poiché A < CF è falso si va in sequenza 4.4 poiché CF < Z è vero si esegue quicksort su LISTA delimitato da A=6 e

Z= 8 4.4.1 siccome A=Z è falso si va in sequenza; 4.4.2 si esegue partizione su LISTA delimitato da A=6 e Z=8

trovando la posizione CF=8 per il separatore 93. 4.4.3 poiché A < CF è vero si esegue quicksort su LISTA delimitato da A=6 e Z= 7

4.4.3.1 siccome A=Z è falso si va in sequenza 4.4.3.2 si esegue partizione su LISTA delimitato da A=6 e Z=7 trovando la

posizione CF=7 per il separatore 81.4.4.3.3 poiché A < CF è vero si esegue quicksort su LISTA delimitato da A=6 e

Z= 6 4.4.3.3.1 siccome A=Z è vero si rientra

4.4.3.4 poiché CF< Z è falso, si rientra 4.4.4 Poiché CF< Z è falso, si rientra



Quicksort: prestazioniQuicksort: prestazioni

• L’algoritmo di quicksort viene utilizzato quando la disposizione degli elementi è il più possibile casuale; in questo caso il numero medio di confronti risulta in ordine di grandezza inferiore al numero di confronti dei metodi visti in precedenza

• Data la complessità dell’analisi del quicksort, ci riferiremo solo al caso migliore: il caso in cui la disposizione di dati è tale che ad ogni passo il perno viene collocato alla metà esatta dell’insieme che si considera (es. 85 32 10 71 63 52 21 101 124 152 112 132 149 96 48).– Supponiamo che la dimensione dell’insieme sia:

N = 2h-1– Il numero dei confronti per ogni passaggio risulta proporzionale ad N,

perché N sono gli elementi globalmente interessati, mentre il numero di passaggi è h-1. Quindi il numero di confronti è proporzionale a N*(h-1).

• Tale ordine risulta valido anche nella media dei casi. • Il caso peggiore si ha quando il vettore è ordinato, caso in cui il

numero di passaggi di partizione è N e il numero di confronti risulta proporzionale ad N2

• La prestazione del metodo per il confronto è influenzata dalla configurazione iniziale dei dati; il numero di spostamenti è certamente inferiore al numero di confronti



Ordinamento per fusioneOrdinamento per fusione

• Sfrutta un problema più semplice dell’ordinamento: quello della fusione:– si parte da due insiemi ordinati, che vengono fusi per

generare un unico insieme ordinato– Si acquisisce un elemento dal primo insieme e uno dal

secondo, vengono confrontati tra loro e si copia nel vettore di destinazione l’elemento più piccolo; si acquisisce un nuovo elemento dall’insieme dove è stata tolto l’elemento e lo si riconfronta con quello rimasto

– Il procedimento ha termine quando sono esaminati tutti gli elementi



Fusione: algoritmo approssimatoFusione: algoritmo approssimato

• L’algoritmo assume che i due insiemi di partenza, di dimensione N ed M, siano contenuti in un vettore V di dimensione N+M. – Il risultato viene posto in un vettore Z, di dimensione

N+M.– L’algoritmo fa uso di tre variabili:

• i è un cursore che delimita in V il primo insieme ordinato di partenza 1≤ i≤ N

• j è un cursore che delimita in V il secondo insieme ordinato di partenza N+1≤ j≤ N+M

• k è un cursore che scorre su tutto il vettore Z 1≤ k≤ N+M



Fusione: flow-chartFusione: flow-chart



Mergesort binario: algoritmo Mergesort binario: algoritmo approssimatoapprossimato

• Ha come base l’algoritmo di fusione • Suddivide gli elementi di V in coppie costituite da elementi

consecutivi (primo-secondo, terzo-quarto,..) e ordina tra di loro gli elementi di una stessa coppia; si ottengono così delle coppie ordinate; a questo punto si ordinano tra di loro gli elementi della prima e della seconda coppia, della terza e della quarta, …. ottenendo alla fine delle quadruple ordinate; si ripete fino ad ottenere un unico insieme ordinato.

• L’algoritmo suppone di partire da un insieme disordinato, di dividerlo in due sezioni e di fondere le due sezioni avendovi prima applicato ricorsivamente l’algoritmo

• Variabili:– Supponiamo che i due insiemi da ordinare siano allocati nel vettore V in

due aree contigue delimitate da u,i la prima e i+1,t la seconda– La variabile i è in sostanza usata per dividere in due l’area di memoria

delimitata da u e t– Il risultato della fusione viene sempre collocato nel vettore Z– Alla fine della fusione supponiamo che in V si ricopi l’insieme ordinato.



Mergesort binario: algoritmo Mergesort binario: algoritmo dettagliatodettagliato

– se u = t allora stop– i = (u+t)/2 – esegui merge sort su V delimitato da u ed i– esegui merge sort su V delimitato da i+1 ed t– esegui fusione su V delimitato da u , i e da i+1, t



Mergesort binario: esempio di Mergesort binario: esempio di applicazioneapplicazione

V ( 34 93 64 25 18 29 76 81 ) N=8 u=1 e t =8

1. siccome u=t è falso si va in sequenza;2. i ← 4 ;3. esegui sort-merge su V delimitato da u=1 e t = 4; 3.1 siccome u=t è falso si va in sequenza; 3.2 i ← 2 ; 3.3 esegui sort-merge su V delimitato da u=1 e t = 2;

3.3.1 siccome u=t è falso si va in sequenza; 3.3.2 i ← 1 ;

3.3.3 esegui sort-merge su V delimitato da u=1 e t = 1; 3.3.3.1 siccome u=t è vero si rientra;

3.3.4 esegui sort-merge su V delimitato da u=2 e t = 2; 3.3.4.1 siccome u = t è vero si rientra;

3.3.5 esegui fusione su V delimitato da u=1 i=1; i+1=2 t=2 3.4 esegui sort-merge su V delimitato da u=3 e t = 4;




3.4.5 esegui fusione su V delimitato da u=1 i=2; i+1=3 t=43.5 esegui fusione su V delimitato da u=1 i=2; i+1=3 t=4



Mergesort binario: esempio di Mergesort binario: esempio di applicazioneapplicazione

4. esegui sort-merge su V delimitato da u=5 e t = 8; 4.1 siccome u=t è falso si va in sequenza; 4.2 i ← 6 ; 4.3 esegui sort-merge su V delimitato da u=5 e t = 6;




4.3.5 esegui fusione su V delimitato da u=5 i=5; i+1=6 t=6 4.4 esegui sort-merge su V delimitato da u=7 e t = 8;




4.4.5 esegui fusione su V delimitato da u=7 i=7; i+1=8 t=84.5 esegui fusione su V delimitato da u=5 i=6; i+1=7 t=85. esegui fusione su V delimitato da u=1 i=4; i+1=5 t=8



Mergesort binario: prestazioniMergesort binario: prestazioni

• L’algoritmo di merge-sort è particolarmente vantaggioso perché il numero di confronti è lo stesso in tutti i casi, anche quello peggiore.

• Il metodo opera partizioni dell’insieme di partenza che sono ad ogni passo della stessa dimensione.

• Supponiamo che la dimensione dell’insieme sia:N= 2h

• Il numero dei confronti per ogni passaggio risulta N, perché N sono gli elementi globalmente interessati, mentre il numero di passaggi è h = log2 N. Quindi il numero di confronti è proporzionale a N*(h) = N * log2 N.

• Al primo passaggio abbiamo N/2 coppie di dimensione N/N/2 =2 su cui applicare l’algoritmo di fusione (per il quale nel caso peggiore si hanno un numero di confronti pari alla grandezza della coppia). Il numero di confronti al primo passo è pertanto (N/2) * 2= N.

• Al secondo passaggio abbiamo N/4 vettori di dimensione N/N/4 =4 su cui applicare l’algoritmo di fusione (per il quale nel caso peggiore si hanno un numero di confronti pari alla grandezza della coppia). Il numero di confronti al secondo passo è pertanto (N/4) * 4 = N.

• Procedendo è facile comprendere che il numero dei confronti risulta N ad ogni passaggio.

Fondamenti di Informatica CDL in Ingegneria Meccanica (B) - A.A. 2009-2010 CDL in Ingegneria...

Documents

Transcript of Fondamenti di Informatica CDL in Ingegneria Meccanica (B) - A.A. 2009-2010 CDL in Ingegneria...