• Non ci sono risultati.

Progetto Corda

N/A
N/A
Protected

Academic year: 2022

Condividi "Progetto Corda"

Copied!
33
0
0

Testo completo

(1)

file:///E:/cordaNoWeb/lez/array.html#3 1/33

Progetto Corda

Alberto Ferrari

Alberto Ferrari

Ingegneria dell'Informazione, UniPR

(2)

file:///E:/cordaNoWeb/lez/array.html#3 2/33

http://www.ce.unipr.it/~aferrari/

Array (ordinamento)

2/33

(3)

file:///E:/cordaNoWeb/lez/array.html#3 3/33

Sort

http://www.ce.unipr.it/~aferrari/

L’ordinamento degli elementi di un array avviene considerando il valore della chiave primaria

Oltre alla valutazione dell’efficienza saranno anche considerate le proprietà di

·

Nei nostri esempi le chiavi saranno numeri interi e la relazione d'ordine totale sarà <=

-

·

stabilità: un algoritmo di ordinamento è stabile se non altera l'ordine relativo di elementi dell'array aventi la stessa chiave primaria

sul posto: un algoritmo di ordinamento opera sul posto se la dimensione delle strutture ausiliarie di cui necessita è indipendente dal numero di elementi dell'array da ordinare

- -

3/33

(4)

file:///E:/cordaNoWeb/lez/array.html#3 4/33

http://www.ce.unipr.it/~aferrari/

insertion sort

4/33

(5)

file:///E:/cordaNoWeb/lez/array.html#3 5/33

insertion sort

http://www.ce.unipr.it/~aferrari/

Al generico passo i l’array è considerato diviso in

·

una sequenza di destinazione a[0] ... a[i - 1] già ordinata

una sequenza di origine a[i] ... a[n - 1] ancora da ordinare

L'obiettivo è di inserire il valore contenuto in a[i] al

posto giusto nella sequenza di destinazione facendolo scivolare a ritroso, in modo da ridurre la sequenza di origine di un elemento

- - -

5/33

(6)

file:///E:/cordaNoWeb/lez/array.html#3 6/33

Esercizio 1

http://www.ce.unipr.it/~aferrari/

Scrivere un programma di ordinamento di un array utilizzando l’algoritmo insertion sort

Calcolare la complessità computazionale

L’algoritmo prodotto è stabile? Opera sul posto?

·

void insertsort(int a[], int n) -

·

nel caso ottimo, pessimo e medio

Definire la classe di complessità asintotica nel caso medio -

-

·

6/33

(7)

file:///E:/cordaNoWeb/lez/array.html#3 7/33

insertion sort

http://www.ce.unipr.it/~aferrari/ 7/33

(8)

file:///E:/cordaNoWeb/lez/array.html#3 8/33

swap function

http://www.ce.unipr.it/~aferrari/

void swap(int *x, int *y) { int temp = *x;

*x = *y;

*y = temp;

}

C

8/33

(9)

file:///E:/cordaNoWeb/lez/array.html#3 9/33

insertion sort in C

http://www.ce.unipr.it/~aferrari/

void insertsort(int array[], int size) { int i, j, app;

for (i=1; i<size; i++) { app = array[i];

j = i-1;

while (j>=0 && array[j]>app) { array[j+1] = array[j];

j--;

}

array[j+1] = app;

} return;

}

C

9/33

(10)

file:///E:/cordaNoWeb/lez/array.html#3 10/33

http://www.ce.unipr.it/~aferrari/

selection sort

10/33

(11)

file:///E:/cordaNoWeb/lez/array.html#3 11/33

selection sort

http://www.ce.unipr.it/~aferrari/

Selection sort è un algoritmo di ordinamento iterativo che, come insertion sort, al generico passo i vede l'array diviso in

una sequenza di destinazione a[0] ... a[i - 1] già ordinata una sequenza di origine a[i] ... a[n - 1] ancora da ordinare L’obiettivo è scambiare il valore minimo della seconda sequenza con il valore contenuto in a[i] in modo da ridurre la sequenza di origine di un elemento

·

·

·

·

11/33

(12)

file:///E:/cordaNoWeb/lez/array.html#3 12/33

Esercizio 2

http://www.ce.unipr.it/~aferrari/

Scrivere un programma di ordinamento di un array utilizzando l’algoritmo selection sort

Calcolare la complessità computazionale

L’algoritmo prodotto è stabile? Opera sul posto?

·

void selectsort(int a[], int n) -

·

nel caso ottimo, pessimo e medio

Definire la classe di complessità asintotica nel caso medio -

-

·

12/33

(13)

file:///E:/cordaNoWeb/lez/array.html#3 13/33

selection sort in C

http://www.ce.unipr.it/~aferrari/

void selectsort(int array[],int size){

int i,j,min;

for (i=0; i<size; i++) { min = i;

for (j=i+1; j<size; j++)

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

if (min != i)

swap(&array[i],&array[min]);

} }

C

13/33

(14)

file:///E:/cordaNoWeb/lez/array.html#3 14/33

http://www.ce.unipr.it/~aferrari/

bubble sort

14/33

(15)

file:///E:/cordaNoWeb/lez/array.html#3 15/33

Bubblesort

http://www.ce.unipr.it/~aferrari/

bubblesort è un algoritmo di ordinamento iterativo che, come insertsort, al generico passo i vede l'array diviso in una sequenza di destinazione a[0] ... a[i - 1] già ordinata una sequenza di origine a[i] ... a[n - 1] ancora da ordinare L’obiettivo è di far emergere (come se fosse una

bollicina) il valore minimo della sequenza di origine

confrontando e scambiando sistematicamente i valori di elementi adiacenti a partire dalla fine dell’array, in modo da ridurre la sequenza di origine di un elemento

·

·

·

·

15/33

(16)

file:///E:/cordaNoWeb/lez/array.html#3 16/33

Esercizio 3

http://www.ce.unipr.it/~aferrari/

Scrivere un programma di ordinamento di un array utilizzando l’algoritmo bubble sort

Calcolare la complessità computazionale

L’algoritmo prodotto è stabile? Opera sul posto?

·

void bubblesort(int a[], int n) -

·

nel caso ottimo, pessimo e medio

Definire la classe di complessità asintotica nel caso medio -

-

·

16/33

(17)

file:///E:/cordaNoWeb/lez/array.html#3 17/33

Migliorabile?

http://www.ce.unipr.it/~aferrari/

Se in una iterazione non avvengono più scambi ???

Esercizio 4

modificare l’algoritmo

rivalutare la complessità computazionale

·

·

·

·

17/33

(18)

file:///E:/cordaNoWeb/lez/array.html#3 18/33

bubble sort in C

http://www.ce.unipr.it/~aferrari/

void bubble_sort(int array[], int size) { int i,last;

for (last = size - 1; last > 0; last-- ){

for (i=0; i<last; i++){

if (array[i]>array[i+1])

swap(&array[i],&array[i+1]);

} } }

C

18/33

(19)

file:///E:/cordaNoWeb/lez/array.html#3 19/33

http://www.ce.unipr.it/~aferrari/

merge sort

19/33

(20)

file:///E:/cordaNoWeb/lez/array.html#3 20/33

Merge sort

http://www.ce.unipr.it/~aferrari/

Algoritmo di ordinamento basato su confronti che utilizza un processo di risoluzione ricorsivo, sfruttando la tecnica del Divide et Impera, che consiste nella suddivisione del problema in sottoproblemi della stessa natura di dimensione via via più piccola.

·

20/33

(21)

file:///E:/cordaNoWeb/lez/array.html#3 21/33

Merge sort

http://www.ce.unipr.it/~aferrari/

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

Altrimenti:

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)

Ognuna di queste sottosequenze viene ordinata, applicando ricorsivamente l'algoritmo(impera)

Le due sottosequenze ordinate vengono fuse (combina).

Per fare questo, si estrae ripetutamente il minimo delle due sottosequenze e lo si pone nella sequenza in uscita, che risulterà ordinata

·

·

·

·

·

·

21/33

(22)

file:///E:/cordaNoWeb/lez/array.html#3 22/33

Divide et impera

http://www.ce.unipr.it/~aferrari/ 22/33

(23)

file:///E:/cordaNoWeb/lez/array.html#3 23/33

Esempio

http://www.ce.unipr.it/~aferrari/

Partenza: [10 3 15 2 1 4 9 0]

l'algoritmo procede ricorsivamente dividendola in metà successive, fino ad arrivare alle coppie [10 3] [15 2] [1 4] [9 0]

A questo punto si fondono (merge) in maniera ordinata gli elementi, riunendo le metà: [3 10] [2 15] [1 4] [0 9]

Al passo successivo, si fondono le coppie di array di due elementi: [2 3 10 15]

[0 1 4 9]

Infine, fondendo le due sequenze di quattro elementi, si ottiene la sequenza ordinata: [0 1 2 3 4 9 10 15]

·

·

·

·

·

23/33

(24)

file:///E:/cordaNoWeb/lez/array.html#3 24/33

merge sort in C

http://www.ce.unipr.it/~aferrari/

void merge_sort(int array[], int left, int right) { int center; // middle index

if(left<right) {

center = (left+right)/2;

merge_sort(array, left, center); //sort first half merge_sort(array, center+1, right); //sort first half merge(array, left, center, right); //merge sorted arrays }

}

C

24/33

(25)

file:///E:/cordaNoWeb/lez/array.html#3 25/33

funzione merge in C

http://www.ce.unipr.it/~aferrari/

void merge(int array[], int left, int center, int right) {

int i = left; //index first array int j = center+1; //index second array

int k = 0; //index new temporary array int temp[DIM_ARRAY]; //temporary array

while ((i<=center) && (j<=right)) {

if (array[i] <= array[j]) { temp[k] = array[i]; i++; } else { temp[k] = array[j]; j++; } k++;

}

while (i<=center) { temp[k] = array[i]; i++; k++; } while (j<=right) { temp[k] = array[j]; j++; k++; } for (k=left; k<=right; k++){ array[k] = temp[k-left]; } }

C

25/33

(26)

file:///E:/cordaNoWeb/lez/array.html#3 26/33

Esercizio 5

http://www.ce.unipr.it/~aferrari/

Scrivere un programma di ordinamento di un array utilizzando l’algoritmo merge sort

Calcolare la complessità computazionale

L’algoritmo prodotto è stabile? Opera sul posto?

·

void mergesort(int a[], int left, int right) -

·

·

26/33

(27)

file:///E:/cordaNoWeb/lez/array.html#3 27/33

Merge sort

http://www.ce.unipr.it/~aferrari/

E' stabile: il confronto tra array[i] e array[j] effettuato nella fusione ordinata usa <=

Non opera sul posto: nella fusione usa un array di appoggio il cui numero di elementi è proporzionale al numero di elementi dell’array da ordinare

La complessità asintotica è T (n) = O(n · log n)

·

·

·

27/33

(28)

file:///E:/cordaNoWeb/lez/array.html#3 28/33

http://www.ce.unipr.it/~aferrari/

quick sort

28/33

(29)

file:///E:/cordaNoWeb/lez/array.html#3 29/33

Quicksort

http://www.ce.unipr.it/~aferrari/

Quicksort è un algoritmo di ordinamento ricorsivo proposto da Hoare nel 1962 Data una porzione di un array e scelto un valore v detto pivot contenuto in

quella porzione, quicksort divide la porzione in tre parti

poi applica l’algoritmo stesso alla prima e alla terza parte

Quicksort determina la tripartizione effettuando degli scambi di valori ≥ v

incontrati a partire dall’inizio della porzione di array con valori ≤ v incontrati a partire dalla fine della porzione di array, in modo tale da spostare i primi

verso la fine della porzione di array e gli ultimi verso l’inizio della porzione dell'array

·

·

la prima composta da elementi contenenti valori ≤ v

la seconda (eventualmente vuota) composta da elementi contenenti valori

= v

la terza composta da elementi contenenti valori ≥ v -

- -

·

·

29/33

(30)

file:///E:/cordaNoWeb/lez/array.html#3 30/33

quick sort in C

http://www.ce.unipr.it/~aferrari/

void quick_sort(int array[], int left, int right) { int p_index; // pivot index

if( left < right ) {

p_index = partition( array, left, right);

quick_sort( array, left, p_index-1);

quick_sort( array, p_index+1, right);

} }

C

30/33

(31)

file:///E:/cordaNoWeb/lez/array.html#3 31/33

funzione di partizionamento in C

http://www.ce.unipr.it/~aferrari/

int partition( int array[], int left, int right) { int pivot; //pivot

int i; //index first part int j; //index second part int temp;

pivot = array[left];

i = left;

j = right+1;

while( 1 ){

do ++i; while( array[i] <= pivot && i <= right );

do --j; while( array[j] > pivot );

if( i >= j ) break;

temp = array[i]; array[i] = array[j]; array[j] = temp;

}

temp = array[left]; array[left] = array[j]; array[j] = temp;

return j;

}

C

31/33

(32)

file:///E:/cordaNoWeb/lez/array.html#3 32/33

Quicksort

http://www.ce.unipr.it/~aferrari/

non è stabile in quanto nel confronto tra array[i] e pivot viene usato < anziché

<= e nel confronto tra array[j] e pivot viene usato > anziché >= Questo è inevitabile al fine di ottenere una corretta tripartizione

Opera sul posto in quanto usa soltanto due variabili aggiuntive (pivot e tmp)

·

·

32/33

(33)

file:///E:/cordaNoWeb/lez/array.html#3 33/33

Alberto Ferrari

Ingegneria dell'Informazione, UniPR

www.ce.unipr.it/~aferrari/

Riferimenti

Documenti correlati

Esercizio 9 Un discriminatore d’ampiezza `e un circuito che consente la trasmissione di una parte sola di una generica forma d’onda

Infine recentemente, analizzando 132 carcinomi del colon-retto, caratterizzati da instabilità cromosomica (CIN), sono state identificate 11 mutazioni somatiche in quattro

Un secondo progetto sulla fontana nel cortile del Dini è simile al primo, con sette vasche di forma semisferica sovrapposte; la prima vasca contiene 5 litri d’acqua e ogni

IMPORTANTE: Utilizzare una funzione per creare la lista, un'altra per stamparla e una terza per stampare la sottolista di

Nel sistema illustrato in figura 1 il blocco di massa M =3kg ` e collegato ad un blocco di massa m, poggiato su un piano inclinato rispetto all’orizzontale di un angolo α=30 o , che

Una popolazione di batteri, inizialmente composta da 8 ∗ 10 4 unit` a, cresce giornalmente del 70% per 4 giorni, quindi decresce del 50% giornaliero per 3 giorni.. Qual `e

Il punto prosegue con velocità v 1 lungo un piano orizzontale liscio e urta in modo completamente anelastico un punto fermo di massa M. Si osserva che dopo l’urto l’energia

L’allievo dovrà elaborare gli schemi di collegamento ed il programma per il PLC, digitare il programma medesimo e collaudarlo in condizioni simulate, realizzare il cablaggio