Algoritmi su Array Algoritmi su Array

(1)

Algoritmi su Array Algoritmi su Array

Moreno Marzolla

Dipartimento di Informatica—Scienza e Ingegneria (DISI) Università di Bologna https://www.moreno.marzolla.name/

(2)

Algoritmi su Array 2

(3)

Ringraziamenti

●

prof. Stefano Mizzaro, Università di Udine

–

http://users.dimi.uniud.it/~stefano.mizzaro/

(4)

Esempi classici con array

●

Inversione

●

Ricerca lineare

●

Ricerca binaria

●

Ordinamento

(5)

Inversione

(6)

Inversione di un array

●

Scambiare di posto gli elementi di un array a[] di n elementi

–

Scambiare il primo con l’ultimo...

–

...Il secondo con il penultimo...

–

...

7 12 3 -1 8 2 1 3 2 15

15 2 3 1 2 8 -1 3 12 7

Prima

Dopo

(7)

Come (non) scambiare il valore di due variabili

●

Quale è il risultato del frammento di codice sopra?

int a = 3, b = 5;

/ modo SBAGLIATO di scambiare tra loro i valori di a e b /

a = b;

b = a;

(8)

Come scambiare il valore di due variabili

●

3 bicchieri, a, b e tmp ("temporaneo")

●

In a c’è acqua, in b c’è vino, tmp è vuoto

●

Voglio “scambiare” a e b (mettere il vino in a e l’acqua in b). Come faccio?

a b

tmp

/* modo CORRETTO di scambiare a e b */

int a = 3, b = 5, tmp;

(9)

Come scambiare il valore di due variabili

●

3 bicchieri, a, b e tmp ("temporaneo")

●

In a c’è acqua, in b c’è vino, tmp è vuoto

●

Voglio “scambiare” a e b (mettere il vino in a e l’acqua in b). Come faccio?

a b

tmp

int a = 3, b = 5, tmp;

tmp = a; /* copia a in tmp */

(10)

Come scambiare il valore di due variabili

●

3 bicchieri, a, b e tmp ("temporaneo")

●

In a c’è acqua, in b c’è vino, tmp è vuoto

●

Voglio “scambiare” a e b (mettere il vino in a e l’acqua in b). Come faccio?

a b

tmp

int a = 3, b = 5, tmp;

a = b; /* copia b in a */

(11)

Come scambiare il valore di due variabili

●

3 bicchieri, a, b e tmp ("temporaneo")

●

In a c’è acqua, in b c’è vino, tmp è vuoto

●

Voglio “scambiare” a e b (mettere il vino in a e l’acqua in b). Come faccio?

a b

tmp

int a = 3, b = 5, tmp;

a = b; /* copia b in a */

b = tmp; /* copia tmp in a */

(12)

Inversione di un array

int i, tmp;

for (i=0; i<n; i++) { tmp = a[n-1-i];

a[n-1-i] = a[i];

a[i] = tmp;

}

SBAGLIATO

9 10 11 12 13

i=0

(13)

Inversione di un array

int i, tmp;

for (i=0; i<n; i++) { tmp = a[n-1-i];

a[n-1-i] = a[i];

a[i] = tmp;

}

SBAGLIATO

9 10 11 12

13

i=1

(14)

Inversione di un array

int i, tmp;

for (i=0; i<n; i++) { tmp = a[n-1-i];

a[n-1-i] = a[i];

a[i] = tmp;

}

SBAGLIATO

9 10

11 12

13

i=2

(15)

Inversione di un array

int i, tmp;

for (i=0; i<n; i++) { tmp = a[n-1-i];

a[n-1-i] = a[i];

a[i] = tmp;

}

SBAGLIATO

9 10

11 12

13

i=3

(16)

Inversione di un array

int i, tmp;

for (i=0; i<n; i++) { tmp = a[n-1-i];

a[n-1-i] = a[i];

a[i] = tmp;

}

SBAGLIATO

9 10 11 12

13

i=4

(17)

Inversione di un array

int i, tmp;

for (i=0; i<n; i++) { tmp = a[n-1-i];

a[n-1-i] = a[i];

a[i] = tmp;

}

SBAGLIATO

13 10 11 12

9 Alla fine riotteniamo l'array di partenza!

(18)

L’algoritmo

●

Scambio il primo con l'ultimo...

●

...il secondo con il penultimo...

●

...fino a metà array!

i = 0;

while ("non sono arrivato a metà") {

"scambia a[i] con a[n-1-i]"

i = i + 1;

}

(19)

L’algoritmo (meglio)

●

Scambio il primo con l'ultimo...

●

...il secondo con il penultimo...

●

...fino a metà array!

i = 0;

j = n-1;

while ("non sono arrivato a metà") {

"scambia a[i] con a[j]"

i = i + 1;

j = j – 1;

}

(20)

L'algoritmo

●

Come decido se non sono ancora arrivato a metà?

7 12 3 -1 8 2 1 3 2 15

i j

7 12 3 -1 8 2 1 3 2 15

i j

i = 0;

j = n-1;

while (i < j) {

i = i + 1;

j = j – 1;

}

(21)

Inversione di un array

/* inversione.c : inverte il contenuto di un array */

#include <stdio.h>

void inverti(int a[], int n) {

int i = 0, j = n-1, tmp;

while ( i < j ) {

tmp = a[i]; a[i] = a[j]; a[j] = tmp;

i = i + 1;

j = j – 1;

} }

#define N 10

int main( void ) {

int a[N], i;

printf("Digita %d valori\n", N);

for (i = 0; i < N; i++) { /* Lettura dell'array */

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

}

inverti(a, N);

for (i = 0; i < N; i++) { /* Stampa l'array dopo l'inversione */

printf("%d\n", a[i]);

}

return 0;

}

(22)

Ricerca lineare

(23)

Ricerca lineare

●

Dati

– Un array a[] di int di lunghezza n

– Un intero k

●

int ricerca(int a[], int n, int k)

– Restituisce la posizione di una occorrenza (la prima?) di k in a[]

– Se k non compare in a, restituisce -1

●

Procedimento

– Scorro l’array partendo dall’inizio

– Fermandomi se trovo un elemento il cui valore è uguale a k, oppure se arrivo in fondo all'array

7 12 3 -1 8 2 1 3 2 15

a[]

k 3

0 1 2 3 4 5 6 7 8 9

(24)

Ricerca lineare

int ricerca(int a[], int n, int k) {

int i;

for (i = 0; i < n; i++) { if (a[i] == k) {

**return i; /* trovato */**

} }

return -1; **/* non trovato */**

}

7 12 3 -1 8 2 1 3 2 15

a[]

k 3

0 1 2 3 4 5 6 7 8 9

(25)

/* ricerca-lineare.c */

int ricerca(int a[], int n, int k) {

int i;

for (i = 0; i < n; i++) { if (a[i] == k) {

return i;

} }

return -1;

}

int a[] = {7, 12, 3, -1, 8, 2, 1, 3, 2, 15};

const int N = sizeof(a) / sizeof(a[0]);

printf("ricerca 7 = %d\n", ricerca(a, N, 7));

return 0;

}

Ricordare che l'istruzione return termina immediatamente l'esecuzione della funzione, restituendo il valore indicato

Ricerca lineare

(26)

Una applicazione della ricerca lineare

●

Il sindaco di Paperopoli ha deciso di tassare i residenti in base al reddito.

●

Detto R il reddito lordo annuo, l'importo dovuto in tasse è (R ´ x), dove x dipende da R secondo la seguente tabella

–

Se 0 ≤ R < 10000 → x = 0.05

–

Se 10000 ≤ R < 22000 → x = 0.11

–

Se 22000 ≤ R → x = 0.15

●

Scrivere un programma in C che chiede all'utente di inserire il reddito R (tipo double; se l'utente inserisce un valore negativo, richiederlo), e stampa l'importo

dovuto in tasse

(27)

/* tasse-1.c */

double R, x;

do {

printf("Inserire reddito R\n");

scanf("%lf", &R);

} while (R < 0);

if ( R < 10000.0) { x = 0.05;

} else {

if ( R < 22000.0 ) { x = 0.11;

} else {

x = 0.15;

} }

printf("Le tasse dovute ammontano a %f\n", R*x);

return 0;

}

Primo tentativo: funziona, ma...

(28)

Un bel giorno...

●

Vista la situazione disastrata delle finanze di

Paperopoli, il sindaco decide di introdurre nuovi scaglioni:

–

Se 0 ≤ R < 10000 → x = 0.05

–

Se 10000 ≤ R < 22000 → x = 0.11

–

Se 22000 ≤ R < 35000 → x = 0.15

–

Se 35000 ≤ R < 45000 → x = 0.17

–

Se 45000 ≤ R < 57000 → x = 0.20

–

Se 57000 ≤ R → x = 0.25

●

Modificare il programma precedente per funzionare

correttamente nella nuova situazione

(29)

Algoritmi su Array 29 /* tasse-2.c */

int main( void ) { double R, x;

do {

scanf("%lf", &R);

} while (R < 0);

if ( R < 10000.0) { x = 0.05;

} else {

if ( R < 22000.0 ) { x = 0.11;

} else {

if ( R < 35000.0 ) { x = 0.15;

} else {

if ( R < 45000.0 ) { x = 0.17;

} else {

if ( R < 57000.0 ) { x = 0.20;

} else {

x = 0.25;

} } }

}

}printf("Le tasse dovute ammontano a %f\n", R*x);

return 0;

}

(30)

(31)

Idea

●

Memorizzo gli scaglioni e le relative percentuali in una tabella

–

cioè in un array

●

Dato il reddito R, cerco nell'array lo scaglione

corrispondente e da questo ricava la percentuale

●

Se gli estremi degli scaglioni e/o le percentuali

cambiano, devo cambiare solo l'array e non il

programma che fa la ricerca!

(32)

/* tasse-4.c */

double scaglioni[]={ 0.0, 10000.0, 22000.0, 35000.0, 45000.0, 57000.0};

double imposta[] ={0.05, 0.11, 0.15, 0.17, 0.20, 0.25};

const int N = sizeof(scaglioni) / sizeof(scaglioni[0]);

double R, x;

int i;

do {

scanf("%lf", &R);

} while (R < 0);

for (i=N-1; R < scaglioni[i]; i--) ; x = imposta[i];

printf("Le tasse dovute ammontano a %f (imposta=%f%%)\n", R*x, x*100);

return 0;

}

Nuova soluzione

scaglioni[i] è il limite inferiore dello scaglione i-esimo (inizio

a contare da i = 0).

imposta[i] è la percentuale di tasse per i redditi appartenenti

allo scaglione i-esimo

Corpo del ciclo "for" vuoto!

(33)

Ricerca Binaria

(34)

Ricerca binaria

●

Dati:

–

Un array di valori interi distinti v[0], v[1], … v[n-1] ordinati in senso crescente (v[0] < v[1] < … < v[n-1])

–

Un valore intero k (arbitrario)

●

Determinare la posizione di k nell'array (se presente)

–

Cioè determinare l'indice i, se esiste, tale che v[i] == k

–

Se k non compare nell'array, restituire -1

●

Es:

2 3 7 12 21 27

v[0] v[1] v[2] v[3] v[4] v[5]

Cerchiamo k = 7

La funzione restituisce 2

(35)

Esempio

●

Ricerca di k = 7

2 3 7 12 18 21 27

(36)

Esempio

●

Ricerca di k = 7

2 3 7 12 18 21 27

(37)

Esempio

●

Ricerca di k = 7

2 3 7 12 18 21 27

(38)

Esempio

●

Ricerca di k = 7

2 3 7 12 18 21 27

(39)

Esempio

●

Ricerca di k = 7

2 3 7 12 18 21 27

(40)

Esempio

●

Ricerca di k = 7

2 3 7 12 18 21 27

Trovato!

(41)

Esempio

●

Ricerca di k = 20

2 3 7 12 18 21 27

(42)

Esempio

●

Ricerca di k = 20

2 3 7 12 18 21 27

(43)

Esempio

●

Ricerca di k = 20

2 3 7 12 18 21 27

(44)

Esempio

●

Ricerca di k = 20

2 3 7 12 18 21 27

(45)

Esempio

●

Ricerca di k = 20

2 3 7 12 18 21 27

(46)

Esempio

●

Ricerca di k = 20

2 3 7 12 18 21 27

(47)

Esempio

●

Ricerca di k = 20

2 3 7 12 18 21 27

Non trovato!

(48)

Domande

●

Dato un array ordinato di n elementi (con n "grande"):

–

Quanti elementi bisogna esaminare nel caso migliore?

–

Quanti elementi bisogna esaminare nel caso peggiore?

(49)

Funzionamento dell'algoritmo

●

Usiamo due valori interi i (inizio) e f (fine) per rappresentare la posizione (indice) del primo e dell'ultimo elemento della porzione di array in cui potrebbe trovarsi il valore cercato

●

Indichiamo con m (mezzo) l'indice dell'elemento che occupa la posizione centrale nel sottovettore v[i] … v[f]

2 3 7 12 18 21 27

v[0] v[1] v[2] v[3] v[4] v[5] v[6]

i=0 m=3 f=6

(50)

Schema di soluzione

int ricbinaria(int v[], int n, int k) {

int i = 0, f = n-1, m;

while (“sottovettore non vuoto”) {

m = “posizione centrale nel sottovettore v[i..f]”;

if (v[m] == k) {

return m; /* trovato in posizione m */

} else {

“aggiorna gli estremi i e f”

} }

return -1; /* non trovato */

}

(51)

Primo raffinamento

●

Come facciamo a "calcolare la posizione centrale nel sottovettore v[i..f]" ?

i ^m

f

(f – i + 1) elementi

Circa (f – i)/2 elementi Circa (f – i)/2 elementi

m = i + (f – i) / 2 = (i + f) / 2

...

(52)

Attenzione...

●

Controlliamo se funziona anche in casi particolari

i = 1 f = 2

m = (1 + 2) / 2 = 1

i = 4 f = 4

m = (4 + 4) / 2 = 4

(53)

Primo raffinamento

int i = 0, f = n-1, m;

while (“sottovettore non vuoto”) { m = (i + f)/2;

if (v[m] == k) {

} else {

“aggiorna gli estremi i e f”

} }

return -1; /* non trovato */

}

(54)

Secondo raffinamento

●

Se il valore centrale non è quello cercato, come aggiornare il valore di i ed f ?

–

Caso 1: il valore centrale è troppo grande (es., cerchiamo 3, valore centrale è 12)

2 3 7 12 18 21 27

i m f

2 3 7 12 18 21 27

i f

(55)

Secondo raffinamento

●

Se il valore centrale non è quello cercato, come aggiornare il valore di i ed f ?

–

Caso 2: il valore centrale è troppo piccolo (es., cerchiamo 21, valore centrale è 12)

2 3 7 12 18 21 27

i m f

2 3 7 12 18 21 27

i f

(56)

Secondo raffinamento

int i = 0, f = n-1, m;

while (“sottovettore non vuoto”) { m = (i + f)/2;

if (v[m] == k) {

} else {

if (v[m] > k) { f = m - 1;

} else {

i = m + 1;

} }

}

i m f

(57)

Raffinamento finale

●

L'algoritmo termina quando non ci sono più elementi da esaminare

●

Es: cerchiamo k = 13

2 12 15

i = 0 m = 1 f = 2

i = 2 m = 2 f = 2

f = 1 i = 2

int i = 0, f = n-1, m;

while (i <= f) { m = (i + f)/2;

if (v[m] == k) { return m;

} else {

if (v[m] > k) { f = m - 1;

} else {

i = m + 1;

} }

}

return -1;

}

(58)

/* ricerca-binaria.c */

int i = 0, f = n-1, m;

while (i <= f) {

m = (i + f) / 2;

if (v[m] == k) {

} else {

if (v[m] > k) { f = m - 1;

} else {

i = m + 1;

} }

}

int a[] = {-1, 1, 2, 3, 7, 15, 16, 18, 20, 21};

const int N = sizeof(a) / sizeof(a[0]);

printf("ricerca 7 = %d\n", ricbinaria(a, N, 7));

printf("ricerca -1 = %d\n", ricbinaria(a, N, -1));

printf("ricerca 17 = %d\n", ricbinaria(a, N, 17));

printf("ricerca -2 = %d\n", ricbinaria(a, N, -2));

return 0;

}

Cosa succede se la funzione ricbinaria() viene invocata su un array vuoto (n = 0)?

Cosa succede se l'array contiene valori duplicati?

.

(59)

Ordinamento

(60)

Ordinamento

●

Ordinare un array, ad es., in ordine crescente

–

Problema classico

–

Capita spesso in moltissime applicazioni

●

Vari algoritmi

●

Ne vediamo uno (Selection Sort)

–

Semplice da capire

–

Non molto efficiente

(61)

Selection Sort

●

Cerco il minimo in a[0]...a[n-1] e lo scambio con a[0]

●

Cerco il minimo in a[1]...a[n-1] e lo scambio con a[1]

●

...

●

Cerco il minimo in a[i]...a[n-1] e lo scambio con a[i]

●

...

12 7 3 2 14 22 1 3

3 7 3 2 14 22 12 1

3 2 3 7 14 22 12 1

7 2 3 3 14 22 12 1

14 2 3 3 7 22 12

1

14 2 3 3 7 12 22

1

22 2 3 3 7 12 14

1

(62)

Schema di soluzione

void selectionsort(int a[], int n) {

int i, ...;

for (i=0; i<n-1; i++) {

"Trova la posizione imin del valore minimo nel sottovettore a[i..n-1]"

"Scambia a[i] con a[imin]"

} }

(63)

Esempio

12 7 3 2 14 22 1 3

i imin

(64)

Esempio

12 7 3 2 14 22

1 3

i imin

(65)

Esempio

12 7

3 2 14 22

1 3

i

imin

(66)

Esempio

12 7

3 2 14 22

1 3

i imin

(67)

Esempio

12 7 3

2 14 22

1 3

i imin

(68)

Esempio

12 7

3 2 22 14

1 3

i imin

(69)

Esempio

12 7

3 2 22 14

1 3

i imin

(70)

Esempio

12 7

3 2 14 22

1 3

i

(71)

Esempio

12 7

3 2 14 22

1 3

(72)

/* selection-sort2.c */

int i, j, tmp;

for (i = 0; i < n - 1; i++) {

/* cerca la posizione del minimo in a[i..n-1] */

int imin = i;

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

if (a[j] < a[imin]) { imin = j; } }

tmp = a[i]; /* scambio a[i] con a[imin] */

a[i] = a[imin];

a[imin] = tmp;

/* qui a[0..i] contiene i primi (i+1) elementi ordinati di a[] */

} }

#define N 10

int a[N], i;

for (i = 0; i < N; i++) { scanf("%d", &a[i]); } selectionsort(a, N);

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

}

Implementazione

(73)

Soluzione alternativa

int i, j;

for (i=0; i<n-1; i++) { /* per ogni i=0, … n-2 */

for (j=i+1; j<n; j++) { /* per ogni j=i+1, … n-1 */

if (a[i] > a[j]) {

} }

(74)

Esempio

12 7 3 2 14 22 1 3

i j

(75)

Esempio

12 7 3 2 14 22 1 3

i j

(76)

Esempio

12 7

3 2 14 22 1 3

i j

(77)

Esempio

12 7 3

2 14 22 1 3

i j

(78)

Esempio

12 7 3

2 14 22 1 3

i j

(79)

Esempio

12 7 3

2 14 22 1 3

i j

(80)

Esempio

12 7 3 14 22 2

1 3

i j

(81)

Esempio

12 7 3 14 22 2

1 3

i j

(82)

Costo computazionale

●

Quante volte viene eseguito il blocco di codice evidenziato?

int i, j;

for (i=0; i<n-1; i++) { /* per ogni i=0, … n-2 */

for (j=i+1; j<n; j++) { /* per ogni j=i+1, … n-1 */

if (a[i] > a[j]) {

} }

(83)

0 1 2 3 4 n-2

i → n - 1

= una iterazione del ciclo "for" interno (quello con indice j)

(84)

0 1 2 3 4 n-2

i → n - 1

(85)

0 1 2 3 4 n-2

i → n - 1

n - 1

n

1+2+…+(n−1) = parte grigia = n(n−1)

2

(86)

Selection Sort

/* selection-sort.c */

int i, j, tmp;

for (i = 0; i < n - 1; i++) {

for (j = i + 1; j < n; j++) { if (a[i] > a[j]) {

tmp = a[i]; /* scambio a[i] con a[j] */

a[i] = a[j];

a[j] = tmp;

} }

/* qui si ha che a[0..i] contiene i primi (i+1) elementi ordinati di a[] /*

} }

#define N 10

int a[N], i;

for (i = 0; i < N; i++) { scanf("%d", &a[i]); } selectionsort(a, N);

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

}

Algoritmi su Array Algoritmi su Array