Algoritmi e strutture dati - Appunti

Caso peggiore: 5

Lavora con un ciclo for esterno e con un while interno:

1. Ad ogni iterazione il ciclo for assegna all’indice j il valore di i (di partenza i=1);

2. While: Finché l’indice j è maggiore di 0 && l’elemento in posizione j è minore dell’elemento in posizione j-1

avverrà uno scambio tra i due elementi e verrà decrementata la j;

3. Quando la j raggiunge lo 0 oppure l’elemento in posizione j è > dell’elemento in posizione j-1 esci dal while,

incrementi la i, poni j=i e si riprende il ciclo while del punto 2.

public class Insertion{

public static void sort(Comparable[] a)

{int N=a.length;

for(int i=1; i<N; i++)

{int j = i;

while(j>0 && less(a[j],a[j-1]))

{exch(a,j,j-1); j--;}

}

\\... } () ()

L’Insertion sort ha prestazioni lineari quando effettua confronti e scambi per ordinare una sequenza con

inversioni. Cioè, ogni volta che un elemento viene spostato a destra di una posizione il numero di inversioni ad esso

associato diminuisce di 1.

Bubble sort (versione non adattiva) 2

( ).

È stabile ma non è adattivo. Il numero di confronti è sempre

L’algoritmo lavora con due ciclo for innestati:

1. Il ciclo for esterno incrementa la i che parte da 0;

2. Il ciclo for interno che decrementa la j e parte dall’ultima posizione n-1. Continua a scorrere fino a quando la j

è maggiore della i confrontando gli elementi in posizione j e j-1. Se l’elemento in posizione j è minore

dell’elemento in posizione j-1 li scambia. Decrementa la j e continua;

3. Quando la j è uguale alla i, cioè puntano allo stesso elemento, termina il ciclo interno, incrementa la i e si

riparte dal punto 2.

public class Bubble{

public static void sort(Comparable[] a)

{int N=a.length;

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

for(int j=N-1; j>i; j--)

if (less(a[j],a[j-1])) exch(a,j,j-1);

}

\\...}

Bubble sort (versione adattiva)

().

Il costo nel caso migliore è

Sempre due cicli for innestati:

1. Il primo incrementa la i e inizializza la variabile booleana scambio a false;

2. Il ciclo for più interno decrementa la j che parte dalla fine n-1 e continua finchè j>i confrontando sempre gli

elementi posizione j e j-1, se l’elemento j<j-1 si scambiano e la variabile booleana passa a true; 6

3. Se j=i controlli se sono avvenuti (se scambio=false oppure no), se non sono avvenuti scambi l’algoritmo viene

interrotto con il break se invece sono avvenuti scambi incrementa la i e riprende il ciclo for interno.

public class Bubble{

public static void sort(Comparable[] a)

{boolean scambio; int N=a.length;

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

{scambio=false;

for(int j=N-1;j>i;j--)

if (less(a[j],a[j-1]))

{exch(a,j,j-1);scambio=true;}

if (!scambio) break;

}}

\\...} ()

In caso di prestazioni lineari, il Bubblesort effettua confronti e scambi per ordinare una sequenza i cui elementi

hanno un numero di inversioni associato limitato da una costante c. Cioè, ogni esecuzione del ciclo interno

diminuisce di 1 il numero di inversioni di ciascun elemento. Il numero di iterazioni del ciclo esterno è limitato da c.

().

Il numero di operazione è quindi

Distribution Counting

( + ).

Il costo è

È un algoritmo di ordinamento digitale. Invece di prendere l’intero dato prende la chiave. Le chiavi possono

assumere valori limitati.

Lavora con le seguenti variabili:

 Int N (lunghezza array di dati chiamato a), min (valore minimo), max (valore massimo) e r.

 Int[] count, b.

1. Si assegna a min e max il primo valore dell’array da ordinare (min=a[0], max=a[0]);

2. Con il primo ciclo for si scandiscono tutti gli elementi di a e ad ogni iterazione confronta l’elemento in posizione

a[j] sia minore di min altrimenti controlla che a[j]>max (se lo è aggiorna max);

3. Terminato il primo ciclo crea l’array count di dimensioni r=max-min+1 e l’array b di dimensione n;

4. Con un nuovo ciclo for l’array count viene inizializzato a 0;

5. Nel terzo ciclo for incrementa di 1 l’elemento contenuto nella cella di indirizzo count[a[j]-min];

6. Nel quarto ciclo si prendono 2 celle consecutive (0,1 2,3 3,4) somma i valori in esse contenuti e li sovrascrive

nella 2° cella;

7. Nel quinto ciclo assegna all’array b di posizione [count[a[j]-min]-- -1] il valore di a[j];

8. L’ultimo ciclo for assegna ad a[j] il valore di b[j]. In tutti i cicli for si usa e si incrementa la variabile j che è 0 di

partenza tranne che nel for numero 4 che la j parte da 1.

Spiegazione Distribution Counting

Per prima cosa scansiona l’array alla ricerca del massimo e del minimo. Crea un nuovo array di dimensioni r=max-

min+1 e lo inizializza a 0. Incrementa di 1 l’array appena creato nella posizione dato-min. Successivamente vengono

sommate due a due (riprendendo sempre la seconda). Si va a creare un nuovo array b della stessa dimensione di a.

for(j=0;j<N;j++) b[count[a[j]-min]-- -1=a[j].

Viene poi restituito b. 7

NOTA BENE: in tutti i for si usa e si incrementa la variabile j (j=0 di partenza tranne per il for n° 6 in cui la j parte da 1).

public class DistributionCounting{

public static void sort(int[] a){

int N,min,max,r;int[] count;int[] b;

min=a[0];max=a[0];N=a.length;

for(int j=0; j<N; j++) {

if(min>a[j]) min=a[j];

else if(max<a[j]) max=a[j];}

r=max-min+1; count=new int[r]; b=new int[N];

for(j=0; j<r; j++) count[j] = 0;

for(j=0; i<N; j++) count[a[j]-min]++;

for(j=1; j<r; j++) count[j] += count[j-1];

for(j=0; j<N; j++) b[count[a[j]-min]-- -1]=a[j];

for(j=0; j<N; j++) a[j] = b[j];}

Bucket sort (( + ))

L’algoritmo è stabile (mantiene l’ordine che avevano i dati in precedenza), non è adattivo e ad un costo

dove k è la lunghezza delle parole, n è il numero di parole e m è la cardinalità dell’alfabeto.

Algoritmo usato per ordinare una sequenza di parole di ugual lunghezza. Come funziona:

1. Si crea una coda s di dimensioni NSIMB;

2. Ciclo for con j=lunghezza parola e finchè j>0 si decrementa;

3. Abbiamo un ciclo while che continua finchè la lista di partenza L non è vuota:

a. Si assegna a w la prima parola della lista L e viene cancellata dalla lista;

b. Si assegna ad e il n° nell’alfabeto del carattere della posizione j della stringa w;

c. Alla nuova coda s si accoda in pos e la parola (ovvero la stringa) w;

d. Parte un ciclo for con i=1 che continua a incrementare i finchè è < di NSIMB. Concatena alla prima

della coda s tutte le parole nella posizione i e assegna alla coda in posizione i il valore NULL, assegna

alla lista L la parola della coda in pos[0] (che sarà la concatenazione di tutte le parole ordinate) e

assegna a s[0] il null.

public static void bucketsort(DEQueue<String> l)

{String w; DEQueue<String>[] s;

s= new DEQueue<String>[NSIMB];

for(int j=LENGTHWORD;j>0;j--)

{while(!Is_empty(l))

{w=l.front(); l. delete(1);

e=Digit(w,j);

s[e].enqueue(w);}

for(int i=1; i<NSIMB; i++)

{s[0].chain(s[i]);s[i]=null;}

l=s[0]; s[0]=null;

}}

Mergesort (vettori e liste)

L'algoritmo funziona nel modo seguente:

 Se la sequenza da ordinare ha lunghezza 0 oppure 1, è già ordinata. Altrimenti:

o La sequenza viene divisa (divide) in due metà (se la sequenza contiene un numero dispari di elementi,

viene divisa in due sottosequenze di cui la prima ha un elemento in più della seconda);

o Ognuna di queste sottosequenze viene ordinata, applicando ricorsivamente l'algoritmo mergesort

(impera);

o Le due sottosequenze ordinate vengono fuse insieme (merge). Si estrae ripetutamente il minimo delle

due sottosequenze e lo si pone nella sequenza in uscita, che risulteranno ordinate; 8

L'algoritmo procede ricorsivamente dividendo la sequenza iniziale in metà successive, fino ad arrivare alle coppie di

elementi, a questo punto fonde (merge) in maniera ordinata gli elementi, riunendo via via le metà (che vanno ad

aumentare di dimensioni) fino ad ottenere l’intera sequenza ordinata.

Merge

Input: 2 vettori ordinati

Output: 1 vettore unico ordinato

(1 + 2)

Costo:

Esistono due tipi di merge:

 Merging di vettori (divide et impera):

1. Si spezza il vettore di partenza in 2 sottovettori a[lo….mid] e a[mid+1….hi];

2. Crea un vettore aux di tipo Comparable delle stesse dimensioni del vettore a di partenza;

3. Assegna ad i=lo e j=mid+1;

4. Parte un ciclo for con k=lo che continua a incrementare k finchè è minore o uguali a hi, assegnando ad

aux in posizione k il valore a in posizione k;

5. Ciclo for con gli stessi parametri di prima controlla che se i>mid assegna ad a[k] il valore di aux[j++],

altrimenti se j>hi assegna ad a[k]=aux[i++], altrimenti se aux[j]<aux[i] assegna ad a[k]=aux[j++]

altrimenti a[k]=aux[i++].

public static void merge(Comparable[] a,int lo,int mid,int hi)

{// merge di a[lo..mid] con a[mid+1..hi]

Comparable[] aux;

aux=new Comparable[a.length];

int i=lo,j=mid+1;

for(int k=lo;k<=hi;k++) aux[k]=a[k];

for(int k=lo;k<=hi;k++)

if(i>mid) a[k]=aux[j++];

else if(j>hi) a[k]=aux[i++];

else if(less(aux[j],aux[i])) a[k]=aux[j++];

else a[k]=aux[i++];

}  Merging di liste:

1. Creo lista c di tipo Comparable;

2. Se a è vuota restituisco b, se b è vuota restituisco a;

3. Assegno ad x il primo valore della lista a e assegno ad y il primo valore della lista b;

4. Ciclo while che continua finchè sia x che y sono diversi da null:

i. Se x<y si inserisce in coda alla lista c l’elemento x, si cancella da a il primo elemento e si

memorizza in x il nuovo primo elemento di a;

ii. Altrimenti (x>=y) si inserisce in coda alla lista c l’elemento y, si cancella da b il primo elemento

e si assegna ad y il nuovo primo elemento;

5. Al termine del while se x==null si concatena c con b, altrimenti (se y==null) si concatena c con a; 9

6. Si restituisce c.

List<Comparable>

mergeL(List<Comparable> a,List<Comparable> b)

{List<Comparable> c;

if(a.isEmpty()) return b;

if(b.isEmpty()) return a;

Comparable x=a.Read(1);Comparable y=b.Read(1);

while((x!=null) && (y!=null))

if (less(x,y))

{c.inserisciInCoda(x);a.Delete(1);x=a.Read(1);}

else

{c.inserisciInCoda(y);b.Delete(1);y=b.Read(1);}

if(x==null) Concatena(c,b);

else Concatena(c,a);

return c;

}

Divide et impera

È una tecnica di progettazione in cui, per arrivare alla soluzione finale, il problema viene spezzato in sottoproblemi

di ugual dimensione e si risolvono (ricorsivamente) i sottoproblemi unen