Ordinamento e Ricerca Ordinamento e Ricerca

(1)

Ordinamento e Ricerca Ordinamento e Ricerca

C. Horstmann C. Horstmann Fondamenti di programmazione e Java 2 Fondamenti di programmazione e Java 2 3^ edizione Apogeo 3^ edizione Apogeo trad. Nicola Fanizzi trad. Nicola Fanizzi corso di Programmazione, CdS: Informatica TPS corso di Programmazione, CdS: Informatica TPS Dip. di Informatica, Università degli studi di Bari Dip. di Informatica, Università degli studi di Bari

(2)

2 2

Obiettivi Obiettivi



Studiare diversi algoritmi di ricerca ed ordinamento Studiare diversi algoritmi di ricerca ed ordinamento



Valutare le ampie differenze di prestazioni offerte da Valutare le ampie differenze di prestazioni offerte da algoritmi che svolgono lo stesso compito

algoritmi che svolgono lo stesso compito



Comprendere la notazione O-grande Comprendere la notazione O-grande



Capire come stimare e confrontare le prestazioni Capire come stimare e confrontare le prestazioni degli algoritmi

degli algoritmi



Imparare come misurare l'esecuzione di un Imparare come misurare l'esecuzione di un

programma

(3)

3 3

Selection Sort Selection Sort



Ordina un array trovando ripetutamente il più piccolo Ordina un array trovando ripetutamente il più piccolo elemento della regione di coda non ordinata e

elemento della regione di coda non ordinata e spostandolo davanti

spostandolo davanti



Lento quando lo si fa girare su grandi moli di dati Lento quando lo si fa girare su grandi moli di dati



Esempio: ordinare un vettore di interi Esempio: ordinare un vettore di interi

(4)

4 4

Ordinare un Array di Interi Ordinare un Array di Interi



Trovare il minimo e scambiarlo con il primo elemento Trovare il minimo e scambiarlo con il primo elemento



Trovare il prossimo minimo. È già al posto giusto Trovare il prossimo minimo. È già al posto giusto



Trovare il prossimo minimo e scambiarlo con il primo Trovare il prossimo minimo e scambiarlo con il primo elemento della porzione non ordinata

elemento della porzione non ordinata

(5)

5 5

Ordinare un Array di Interi Ordinare un Array di Interi



Ripeti Ripeti



Quando la porzione disordinata è di lunghezza 1 Quando la porzione disordinata è di lunghezza 1 abbiamo finito

abbiamo finito

(6)

6 6

SelectionSorter.java SelectionSorter.java

01: /**

02: Questa classe ordina un array, 02: Questa classe ordina un array,

03: usando l'algoritmo di selection sort 03: usando l'algoritmo di selection sort 04: */

04: */

05: public class SelectionSorter 05: public class SelectionSorter 06: {

06: {

07: /**

08: costruisce un selection sorter.

09: @param anArray l'array da ordinare 09: @param anArray l'array da ordinare 10: */

10: */

11: public SelectionSorter(int[] anArray) 11: public SelectionSorter(int[] anArray) 12: {

12: {

13: a = anArray;

14: } 14: }

(7)

7 7

SelectionSorter.java SelectionSorter.java

16: /**

17: ordina l'array di questo selection sorter.

18: */

19: public void sort() 19: public void sort() 20: {

20: {

21: for (int i = 0; i < a.length - 1; i++) 21: for (int i = 0; i < a.length - 1; i++) 22: {

22: {

23: int minPos = minimumPosition(i);

24: swap(minPos, i);

25: } 25: } 26: } 26: } 27: 27:

(8)

8 8

SelectionSorter.java SelectionSorter.java

28: /**

29: trova il minimo nella coda dell'array.

30: @param from prima pos. in a da confrontare 30: @param from prima pos. in a da confrontare

31: @return pos. del minimo tra a[from] e a[a.length-1]

33: */

34: private int minimumPosition(int from) 34: private int minimumPosition(int from) 35: {

35: {

36: int minPos = from;

37: for (int i = from + 1; i < a.length; i++) 37: for (int i = from + 1; i < a.length; i++) 38: if (a[i] < a[minPos]) minPos = i;

38: if (a[i] < a[minPos]) minPos = i;

39: return minPos;

40: } 40: } 41: 41:

(9)

9 9

SelectionSorter.java SelectionSorter.java

42: /**

43: scambi due elementi dell'array.

44: @param i pos. del primo elem. da scambiare 44: @param i pos. del primo elem. da scambiare

45: @param j pos. del secondo elem. da scambiare 45: @param j pos. del secondo elem. da scambiare

46: */

47: private void swap(int i, int j) 47: private void swap(int i, int j)

48: { 48: {

49: int temp = a[i];

50: a[i] = a[j];

51: a[j] = temp;

52: } 52: } 53: 53:

54: private int[] a;

55: } 55: }

(10)

10 10

SelectionSortTester SelectionSortTester

01: /**

02: Programma che testa all'algoritmo di selection sort 02: Programma che testa all'algoritmo di selection sort 03: ordinando un array riempito con numeri casuali.

03: ordinando un array riempito con numeri casuali.

04: */

05: public class SelectionSortTester 05: public class SelectionSortTester 06: {

06: {

07: public static void main(String[] args) 07: public static void main(String[] args) 08: {

08: {

09: int[] a = ArrayUtil.randomIntArray(20, 100);

10: ArrayUtil.print(a);

11: 11:

12: SelectionSorter sorter = new SelectionSorter(a);

13: sorter.sort();

14:14:

(11)

11 11

ArrayUtil.java ArrayUtil.java

01: import java.util.Random;

02: 02:

03: /**

04: Classe contenente metodi d'utilità per 04: Classe contenente metodi d'utilità per 05: la manipolazione di array.

05: la manipolazione di array.

06: */

07: public class ArrayUtil 07: public class ArrayUtil 08: {

08: {

09: /**

10: crea un array riempito con valori casuali.

11: @param length lunghezza dell'array 11: @param length lunghezza dell'array

12: @param n numero dei possibili valori casuali 12: @param n numero dei possibili valori casuali 13: @return array riempito con numeri casuali tra 13: @return array riempito con numeri casuali tra 14: 0 e n – 1

14: 0 e n – 1 15: */

15: */

16: public static int[] randomIntArray(int length, int n) 16: public static int[] randomIntArray(int length, int n) 17: {

17: {

18: int[] a = new int[length];

19: for (int i = 0; i < a.length; i++) 19: for (int i = 0; i < a.length; i++) 20: a[i] = generator.nextInt(n);

20: a[i] = generator.nextInt(n);

21:

22: return a;

(12)

12 12

ArrayUtil.java ArrayUtil.java

24: 24:

25: /**

26: stampa tutti gli elementi in un array.

27: @param a l'array da stampare 27: @param a l'array da stampare 28: */

28: */

29: public static void print(int[] a) 29: public static void print(int[] a) 30: {

30: {

31: for (int e : a) 31: for (int e : a)

32: System.out.print(e + " ");

33: System.out.println();

34: } 34: } 35: 35:

36: private static Random generator = new Random();

37: } 37: } 38: 38:

(13)

13 13

SelectionSortTester SelectionSortTester

65 46 14 52 38 2 96 39 14 33 13 4 24 99 89 77 73 87 36 81 65 46 14 52 38 2 96 39 14 33 13 4 24 99 89 77 73 87 36 81 2 4 13 14 14 24 33 36 38 39 46 52 65 73 77 81 87 89 96 99 2 4 13 14 14 24 33 36 38 39 46 52 65 73 77 81 87 89 96 99



Output Output

(14)

14 14

Profilazione dell'Algoritmo Profilazione dell'Algoritmo

Selection Sort Selection Sort



Si intende misurare il tempo impiegato dall'algoritmo Si intende misurare il tempo impiegato dall'algoritmo per l'esecuzione

per l'esecuzione

 Escludendo il tempo occorso per il caricamento del Escludendo il tempo occorso per il caricamento del programma

programma

 Escludendo il tempo necessario all'outputEscludendo il tempo necessario all'output



Si crei una classe Si crei una classe StopWatch StopWatch ( ( cronometro cronometro ) per ) per misurare il tempo d'esecuzione di un algoritmo

misurare il tempo d'esecuzione di un algoritmo

 Può partire fermarsi e fornire il tempo trascorso Può partire fermarsi e fornire il tempo trascorso

(15)

15 15

Profilazione dell'Algoritmo Profilazione dell'Algoritmo

Selection Sort Selection Sort



Si crea un oggetto Si crea un oggetto StopWatch StopWatch

 Si fa partire lo stopwatch subito prima del sort Si fa partire lo stopwatch subito prima del sort

 Si ferma lo stopwatch subito dopo il sort Si ferma lo stopwatch subito dopo il sort

 Si legge il tempo trascorso Si legge il tempo trascorso

(16)

16 16

StopWatch.java StopWatch.java

01: /**

02: Uno stopwatch accumula tempo in fase di run. Lo si può 02: Uno stopwatch accumula tempo in fase di run. Lo si può 03: far partire e fermare ripetutamente. Lo si può usare 03: far partire e fermare ripetutamente. Lo si può usare 04: per misurare il tempo d'esecuzione programma

04: per misurare il tempo d'esecuzione programma 05: */

05: */

06: public class StopWatch 06: public class StopWatch 07: {

07: { 08: /**

08: /**

09: costruisce uno stopwatch nello stato di fermo 09: costruisce uno stopwatch nello stato di fermo 10: e senza tempo accumulato.

10: e senza tempo accumulato.

11: */

12: public StopWatch() 12: public StopWatch() 13: {

13: {

14: reset();

(17)

17 17

StopWatch.java StopWatch.java

17: /**

18: fa partire lo stopwatch. Inizia l'accumulo di tempo.

19: */

20: public void start() 20: public void start() 21: {

21: {

22: if (isRunning) return;

23: isRunning = true;

24: startTime = System.currentTimeMillis();

25: } 25: } 26:

26:

27: /**

28: Ferma lo stopwatch. Ferma l'accumulo di tempo che 28: Ferma lo stopwatch. Ferma l'accumulo di tempo che 29: viene aggiunto al tempo trascorso (elapsed).

29: viene aggiunto al tempo trascorso (elapsed).

30: */

31: public void stop() 31: public void stop() 32: {

32: {

33: if (!isRunning) return;

34: isRunning = false;

35: long endTime = System.currentTimeMillis();

36: elapsedTime = elapsedTime + endTime - startTime;

37: } 37: }

(18)

18 18

StopWatch.java StopWatch.java

39: /**

40: restituisce il tempo totale trascorso.

41: @return tempo totale trascorso 41: @return tempo totale trascorso 42: */

42: */

43: public long getElapsedTime() 43: public long getElapsedTime() 44: {

44: {

45: if (isRunning) 45: if (isRunning) 46: {

46: {

47: long endTime = System.currentTimeMillis();

48: return elapsedTime + endTime - startTime;

49: } 49: } 50: else 50: else

51: return elapsedTime;

52: } 52: } 53:

53:

(19)

19 19

StopWatch.java StopWatch.java

54: /**

55: Ferma il cronometro e resetta l'accumulatore a 0.

56: */

57: public void reset() 57: public void reset() 58: {

58: {

59: elapsedTime = 0;

60: isRunning = false;

61: } 61: } 62:

62:

63: private long elapsedTime;

64: private long startTime;

65: private boolean isRunning;

66: } 66: }

(20)

20 20

SelectionSortTimer SelectionSortTimer

01: import java.util.Scanner;

02: 02:

03: /**

04: Questo programma misura il tempo impiegato ad ordinare 04: Questo programma misura il tempo impiegato ad ordinare 05: un array di grandeza definita dall'utente con il

05: un array di grandeza definita dall'utente con il 06: l'algoritmo di selection sort.

06: l'algoritmo di selection sort.

07: */

08: public class SelectionSortTimer 08: public class SelectionSortTimer 09: {

09: {

11: {

12: Scanner in = new Scanner(System.in);

13: System.out.print("Enter array size: ");

14: int n = in.nextInt();

15: 15:

(21)

21 21

SelectionSortTimer SelectionSortTimer

16: // Costruisce un array casuale 16: // Costruisce un array casuale 17: 17:

18: int[] a = ArrayUtil.randomIntArray(n, 100);

19: SelectionSorter sorter = new SelectionSorter(a);

20:

21: // Usa stopwatch per cronometrare il selection sort 21: // Usa stopwatch per cronometrare il selection sort 22:

22:

23: StopWatch timer = new StopWatch();

24:

25: timer.start();

26: sorter.sort();

27: timer.stop();

28:

29: System.out.println("Elapsed time: "

30: + timer.getElapsedTime() + " milliseconds");

31: } 31: } 32: } 32: } 33: 33:

34: 34:

(22)

22 22

SelectionSortTester SelectionSortTester

Enter array size: 100000 Enter array size: 100000

Elapsed time: 27880 milliseconds Elapsed time: 27880 milliseconds



Output Output

(23)

23 23

Selection Sort Selection Sort su Array di Varie Dimensioni su Array di Varie Dimensioni

27,359 27,359 60,000

60,000

19,015 19,015 50,000

50,000

12,188 12,188 40,000

40,000

6,846 6,846 30,000

30,000

3,051 3,051 20,000

20,000

772772 10,000

10,000

Millisecondi Millisecondi Dim. n

Dim. n

*Obtained with a Pentium processor, 1.2 GHz, Java 5.0, Linux

(24)

24 24

Selection Sort

su Array di Varie Dimensioni

(25)

25 25

Selection Sort Selection Sort su Array di Varie Dimensioni su Array di Varie Dimensioni



Raddoppiando le dimensioni del vettore Raddoppiando le dimensioni del vettore l'algoritmo richiederà per l'ordinamento l'algoritmo richiederà per l'ordinamento

un tempo pari a molto più del doppio

(26)

26 26

Analisi delle Prestazioni Analisi delle Prestazioni dell'Algoritmo di Selection Sort dell'Algoritmo di Selection Sort



In un vettore di dimensioni n, si contino quante volte In un vettore di dimensioni n, si contino quante volte venga

venga visitato visitato un suo elemento un suo elemento

 Per trovare il minimo, si visitano n elementiPer trovare il minimo, si visitano n elementi + 2 visite per lo scambio

+ 2 visite per lo scambio

 Per trovare il prossimo minimo, si visitano (n - 1) elementi Per trovare il prossimo minimo, si visitano (n - 1) elementi + 2 visite per lo scambio

 L'ultimo termine dà 2 elementi visitati per trovare il minimo L'ultimo termine dà 2 elementi visitati per trovare il minimo + 2 visite per lo scambio

(27)

27 27

Analisi delle Prestazioni Analisi delle Prestazioni dell'Algoritmo di Selection Sort dell'Algoritmo di Selection Sort



Numero di visite: Numero di visite:

 n + 2 + (n - 1) + 2 + (n - 2) + 2 + . . .+ 2 + 2 n + 2 + (n - 1) + 2 + (n - 2) + 2 + . . .+ 2 + 2

 Si può semplificare a: nSi può semplificare a: n²²/2 + 5n/2 - 3 /2 + 5n/2 - 3

 5n/2 - 3 è piccolo in confronto a n5n/2 - 3 è piccolo in confronto a n²²/2 /2 per cui lo si può ignorare

per cui lo si può ignorare

 Si ignora anche 1/2 Si ignora anche 1/2

si annulla nel confronto di rapporti si annulla nel confronto di rapporti

(28)

28 28

Analisi delle Prestazioni Analisi delle Prestazioni dell'Algoritmo di Selection Sort dell'Algoritmo di Selection Sort



Il numero delle visite è dell'ordine di Il numero delle visite è dell'ordine di n n

²²



Usando la notazione O-grande: Usando la notazione O-grande:

il numero di visite è

il numero di visite è O(n O(n

²²

) )

 Moltiplicando il numero di elementi di un vettore per 2 si Moltiplicando il numero di elementi di un vettore per 2 si moltiplica il tempo di elaborazione per 4

moltiplica il tempo di elaborazione per 4



Notazione O-grande: Notazione O-grande: f(n) = O(g(n)) f(n) = O(g(n)) esprime il fatto che

esprime il fatto che f f non cresce più velocemente di non cresce più velocemente di g g



Per convertire nella notazione O-grande: Per convertire nella notazione O-grande:

(29)

29 29

Insertion Sort Insertion Sort

 Si assuma che la sequenza inizialeSi assuma che la sequenza iniziale a[0]a[0] . . . . . . a[k]a[k] sia ordinata (k = 0): sia ordinata (k = 0):

 Aggiungere Aggiungere a[1]a[1]

l'elemento deve essere inserito prima di l'elemento deve essere inserito prima di 1111

 Aggiungere Aggiungere a[2]a[2]

(30)

30 30

Insertion Sort Insertion Sort

 aggiungere aggiungere a[3]a[3]

 Infine, aggiungere Infine, aggiungere a[4]a[4]

(31)

31 31

InsertionSorter.java InsertionSorter.java

01: /**

02: Questa classe ordina un array, usando l'algoritmo 02: Questa classe ordina un array, usando l'algoritmo 03:03: di insertion sort di insertion sort

04: */

05: public class InsertionSorter 05: public class InsertionSorter 06: {

06: {

07: /**

08: costruisce un insertion sorter.

10: */

11: public InsertionSorter(int[] anArray) 11: public InsertionSorter(int[] anArray) 12: {

12: {

13: a = anArray;

14: } 14: } 15: 15:

(32)

32 32

InsertionSorter.java InsertionSorter.java

16: /**

17: ordina l'array dato con questo insertion sorter 17: ordina l'array dato con questo insertion sorter 18: */

18: */

20: {

21: for (int i = 1; i < a.length; i++) 21: for (int i = 1; i < a.length; i++) 22: {

22: {

23: int next = a[i];

24: // Move all larger elements up 24: // Move all larger elements up 25: int j = i;

25: int j = i;

26: while (j > 0 && a[j - 1] > next) 26: while (j > 0 && a[j - 1] > next) 27: {

27: {

28: a[j] = a[j - 1];

29: j--;

30: } 30: }

31: // inserisce l'elemento 31: // inserisce l'elemento

(33)

33 33

Merge Sort Merge Sort



Ordina un vettore Ordina un vettore

 Tagliando il vettore in due metàTagliando il vettore in due metà

 Ordinando ricorsivamente entrambe le metàOrdinando ricorsivamente entrambe le metà

 Fondendo le metà ordinateFondendo le metà ordinate



Molto più veloce dei precedenti algoritmi Molto più veloce dei precedenti algoritmi

(34)

34 34

Esempio di Merge Sort Esempio di Merge Sort



Dividere un array in due parti Dividere un array in due parti

ed ordinare ognuna di esse

(35)

35 35

Esempio di Merge Sort Esempio di Merge Sort



Fondere le due metà ordinate in un singolo array Fondere le due metà ordinate in un singolo array ordinato

ordinato

(36)

36 36

Merge Sort Merge Sort

public void sort() public void sort() {{

if (a.length <= 1) return;

int[] first = new int[a.length / 2];

int[] second = new int[a.length – first.length]; int[] second = new int[a.length – first.length];

System.arraycopy(a, 0, first, 0, first.length); System.arraycopy(a, 0, first, 0, first.length);

System.arraycopy(a, first.length, second, 0, second.length); System.arraycopy(a, first.length, second, 0, second.length);

MergeSorter firstSorter = new MergeSorter(first); MergeSorter firstSorter = new MergeSorter(first);

MergeSorter secondSorter = new MergeSorter(second); MergeSorter secondSorter = new MergeSorter(second);

firstSorter.sort(); firstSorter.sort();

(37)

37 37

MergeSorter.java MergeSorter.java

01: /**

02: questa classe ordina un array con l'algoritmo di merge 02: questa classe ordina un array con l'algoritmo di merge sort.

sort.

03: */

04: public class MergeSorter 04: public class MergeSorter 05: {

05: {

06: /**

07: costruisce un merge sorter.

09: */

10: public MergeSorter(int[] anArray) 10: public MergeSorter(int[] anArray) 11: {

11: {

12: a = anArray;

13: } 13: } 14:

14:

(38)

38 38

MergeSorter.java MergeSorter.java

15: /**

16: ordina l'array gestito da questo merge sorter.

17: */

19: {

20: if (a.length <= 1) return;

21: int[] first = new int[a.length / 2];

22: int[] second = new int[a.length - first.length];

23: System.arraycopy(a, 0, first, 0, first.length);

24: System.arraycopy(a, first.length, second, 0, 24: System.arraycopy(a, first.length, second, 0,

second.length);second.length);

25: MergeSorter firstSorter = new MergeSorter(first);

26: MergeSorter secondSorter = new MergeSorter(second);

27: firstSorter.sort();

28: secondSorter.sort();

29: merge(first, second);

(39)

39 39

MergeSorter.java MergeSorter.java

32: /**

33: fonde due array ordinati nell'array gestito da 33: fonde due array ordinati nell'array gestito da 34: questo merge sorter.

34: questo merge sorter.

35: @param first primo array ordinato 35: @param first primo array ordinato 36: @param second secondo array ordinato 36: @param second secondo array ordinato 37: */

37: */

38: private void merge(int[] first, int[] second) 38: private void merge(int[] first, int[] second) 39: {

39: {

40: // fonde le due metà nell'array temporaneo 40: // fonde le due metà nell'array temporaneo 41: 41:

42: int iFirst = 0;

43: // indice prossimo elemento nell'array first 43: // indice prossimo elemento nell'array first 44: int iSecond = 0;

44: int iSecond = 0;

45: // indice prossimo elemento nell'array second 45: // indice prossimo elemento nell'array second 46: int j = 0;

46: int j = 0;

47: // prossima posizione libera in a 47: // prossima posizione libera in a 48: 48:

(40)

40 40

MergeSorter.java MergeSorter.java

49: // Mentre nè iFirst né iSecond superano la fine 49: // Mentre nè iFirst né iSecond superano la fine 50: // copia l'elemento più piccolo in a

50: // copia l'elemento più piccolo in a 51: while (iFirst < first.length &&

51: while (iFirst < first.length &&

iSecond < second.length)iSecond < second.length) 52: {

52: {

53: if (first[iFirst] < second[iSecond]) 53: if (first[iFirst] < second[iSecond]) 54: {

54: {

55: a[j] = first[iFirst];

56: iFirst++;

57: } 57: } 58: else 58: else 59: { 59: {

60: a[j] = second[iSecond];

61: iSecond++;

62: } 62: }

(41)

41 41

MergeSorter.java MergeSorter.java

66: // Notare che solo una delle due chiamate ad 66: // Notare che solo una delle due chiamate ad 67: // arraycopy qui sotto copia elementi

67: // arraycopy qui sotto copia elementi 68: 68:

69: // copia eventuali elementi rimasti nell'array first 69: // copia eventuali elementi rimasti nell'array first 70: System.arraycopy(first, iFirst, a, j,

70: System.arraycopy(first, iFirst, a, j,

first.length - iFirst);first.length - iFirst);

71:

72: // copia eventuali elementi rimasti nell'array 72: // copia eventuali elementi rimasti nell'array second

second

73: System.arraycopy(second, iSecond, a, j, 73: System.arraycopy(second, iSecond, a, j,

second.length - iSecond);second.length - iSecond);

74: } 74: } 75: 75:

77: } 77: }

(42)

42 42

MergeSortTester.java MergeSortTester.java

01: /**

02: questo programma testa l'algoritmo di merge sort 02: questo programma testa l'algoritmo di merge sort 03: ordinando un array riempito di numeri casuali.

03: ordinando un array riempito di numeri casuali.

04: */

05: public class MergeSortTester 05: public class MergeSortTester 06: {

06: {

08: {

11: MergeSorter sorter = new MergeSorter(a);

12: sorter.sort();

14: } 14: } 15: } 15: } 16: 16:

(43)

43 43

MergeSortTester.java MergeSortTester.java



Output: Output:

8 81 48 53 46 70 98 42 27 76 33 24 2 76 62 89 90 5 13 21 8 81 48 53 46 70 98 42 27 76 33 24 2 76 62 89 90 5 13 21 2 5 8 13 21 24 27 33 42 46 48 53 62 70 76 76 81 89 90 98 2 5 8 13 21 24 27 33 42 46 48 53 62 70 76 76 81 89 90 98

(44)

44 44

Analisi dell'Algoritmo Analisi dell'Algoritmo

Merge Sort Merge Sort

19,015 19,015 9797

50,000 50,000

12,188 12,188 8080

40,000 40,000

6,846 6,846 6262

30,000 30,000

3,051 3,051 4747

20,000 20,000

772772 3131

10,000 10,000

Selection Sort Selection Sort

(millisecondi) (millisecondi) Merge Sort

Merge Sort (millisecondi) (millisecondi) nn

(45)

45 45

Merge Sort vs. Selection Sort Merge Sort vs. Selection Sort

Tempi d'Esecuzione Tempi d'Esecuzione

Figure 2:

Merge Sort Timing (blue)

(46)

46 46

Analisi dell'Algoritmo Analisi dell'Algoritmo

Merge Sort Merge Sort



In un array di dim. n, si conti quante volte un In un array di dim. n, si conti quante volte un elemento viene visitato

elemento viene visitato



Si assuma che n sia una potenza di 2: Si assuma che n sia una potenza di 2: n = 2 n = 2

^m^m



Si calcoli il numero di visite per creare i due sotto- Si calcoli il numero di visite per creare i due sotto- array e poi per fondere i due array ordinati

array e poi per fondere i due array ordinati

 3 visite per fondere ogni elemento ossia 3n visite 3 visite per fondere ogni elemento ossia 3n visite

 2n visite per creare i due sotto-vettori2n visite per creare i due sotto-vettori Un totale di 5n visite

Un totale di 5n visite

(47)

47 47

Analisi dell'Algoritmo Analisi dell'Algoritmo

Merge Sort Merge Sort



T(n) T(n) denoti il numero di visite impiegate per ordinare denoti il numero di visite impiegate per ordinare un array di

un array di n n elementi, quindi: elementi, quindi:

 T(n) = T(n/2) + T(n/2) + 5n ossiaT(n) = T(n/2) + T(n/2) + 5n ossia T(n) = 2T(n/2) + 5n

T(n) = 2T(n/2) + 5n



Le visite per un array di dim. Le visite per un array di dim. n/2 n/2 sono: sono:

T(n/2) = 2T(n/4) + 5n/2 T(n/2) = 2T(n/4) + 5n/2

 Per cui: T(n) = 2 × 2T(n/4) +5n + 5n Per cui: T(n) = 2 × 2T(n/4) +5n + 5n



Le visite per un array di dim. Le visite per un array di dim. n/4 n/4 sono: sono:

T(n/4) = 2T(n/8) + 5n/4 T(n/4) = 2T(n/8) + 5n/4

 Per cui: T(n) = 2 × 2 × 2T(n/8) + 5n + 5n + 5n Per cui: T(n) = 2 × 2 × 2T(n/8) + 5n + 5n + 5n

(48)

48 48

Analisi dell'Algoritmo Analisi dell'Algoritmo

Merge Sort Merge Sort



Ripetendo il processo k volte: Ripetendo il processo k volte:

T(n) = 2

^k^k

T(n/2 T(n/2

^k^k

) +5nk ) +5nk



Dato che n = 2 Dato che n = 2

^m^m

, ponendo k = m: , ponendo k = m:

T(n)

T(n) = 2 = 2

^m^m

T(n/2 T(n/2

^m^m

) +5nm = ) +5nm =

= nT(1) + 5nm = = nT(1) + 5nm =

= n + 5n

= n + 5n · · log log

₂₂

(n) (n)

(49)

49 49

Analisi dell'Algoritmo Analisi dell'Algoritmo

Merge Sort Merge Sort



Per stabilire l'ordine di crescita: Per stabilire l'ordine di crescita:

 Lasciamo cadere il termine di ordine inferiore n Lasciamo cadere il termine di ordine inferiore n

 ... il fattore costante 5 ... il fattore costante 5

 ... la base del logaritmo dato che tutti i logaritmi sono ... la base del logaritmo dato che tutti i logaritmi sono collegati da un fattore costante di conversione

collegati da un fattore costante di conversione

 Rimane Rimane n log(n)n log(n)



Usando la notazione O-grande: Usando la notazione O-grande:

il numero delle visite è

il numero delle visite è O(nlog(n)) O(nlog(n))

(50)

50 50

Merge Sort vs. Selection Sort Merge Sort vs. Selection Sort



Il selection sort è un algoritmo O(n2) Il selection sort è un algoritmo O(n2)



Il merge sort è un algoritmo O(nlog(n)) Il merge sort è un algoritmo O(nlog(n))



La funzione nlog(n) cresce molto più lentamente di n La funzione nlog(n) cresce molto più lentamente di n

²²

(51)

51 51

Ordinamento in Programma Java Ordinamento in Programma Java



La classe La classe Arrays Arrays implementa un proprio metodo implementa un proprio metodo di ordinamento

di ordinamento



Per ordinare un vettore di interi Per ordinare un vettore di interi



Questo metodo sort utilizza l'algoritmo Questo metodo sort utilizza l'algoritmo Quicksort

Quicksort (cfr. Argomenti avanzati 17.3) (cfr. Argomenti avanzati 17.3)

int[] a = . . . ; int[] a = . . . ; Arrays.sort(a);

Arrays.sort(a);

(52)

52 52

L' Algoritmo Quicksort L' Algoritmo Quicksort



Tecnica detta Tecnica detta Divide et impera Divide et impera

 Partiziona l'intervallo di elementi Partiziona l'intervallo di elementi

 Ordina ognuna delle partizioniOrdina ognuna delle partizioni

(53)

53 53

L' Algoritmo Quicksort L' Algoritmo Quicksort

public void sort(int from, int to) public void sort(int from, int to) {{

if (from >= to) return;

int p = partition(from, to);

sort(from, p);

sort(p + 1, to);

} }

(54)

54 54

L' Algoritmo Quicksort

(55)

55 55

L' Algoritmo Quicksort L' Algoritmo Quicksort

Figure 4:

(56)

56 56

L' Algoritmo Quicksort L' Algoritmo Quicksort

private int partition(int from, int to) private int partition(int from, int to) {{

int pivot = a[from];

int i = from - 1;

int j = to + 1;

while (i < j) while (i < j) { {

i++; while (a[i] < pivot) i++;

j--; while (a[j] > pivot) j--;

if (i < j) swap(i, j);

} }

return j;

} }

(57)

57 57

Ricerca Ricerca



Ricerca Lineare Ricerca Lineare : detta anche : detta anche ricerca sequenziale ricerca sequenziale



Esamina tutti i valori nell'array fino a trovare una Esamina tutti i valori nell'array fino a trovare una corrispondenza o comunque al termine del vettore corrispondenza o comunque al termine del vettore



Numero di visite per la ricerca lineare Numero di visite per la ricerca lineare in un array di

in un array di n n elementi : elementi :

 In media si vistano In media si vistano n/2n/2 elementi elementi

 Il massimo di visite è Il massimo di visite è nn



Una ricerca lineare trova un valore in un array in Una ricerca lineare trova un valore in un array in

O( O( n n ) passi ) passi

(58)

58 58

LinearSearcher.java LinearSearcher.java

01: /**

02: A class for executing linear searches through an array.

03: */

04: public class LinearSearcher 04: public class LinearSearcher 05: {

05: { 06: /**

06: /**

07: Constructs the LinearSearcher.

08: @param anArray an array of integers 08: @param anArray an array of integers 09: */

09: */

10: public LinearSearcher(int[] anArray) 10: public LinearSearcher(int[] anArray) 11: {

11: {

12: a = anArray;

13: } 13: } 14: 14:

(59)

59 59

LinearSearcher.java LinearSearcher.java

15: /**

16: Finds a value in an array, using the linear search 16: Finds a value in an array, using the linear search 17: algorithm.

17: algorithm.

18: @param v the value to search 18: @param v the value to search

19: @return the index at which the value occurs, or -1 19: @return the index at which the value occurs, or -1 20: if it does not occur in the array

20: if it does not occur in the array 21: */

21: */

22: public int search(int v) 22: public int search(int v) 23: {

23: {

24: for (int i = 0; i < a.length; i++) 24: for (int i = 0; i < a.length; i++) 25: {

25: {

26: if (a[i] == v) 26: if (a[i] == v) 27: return i;

27: return i;

28: } 28: }

29: return -1;

30: } 30: } 31: 31:

33: } 33: }

(60)

60 60

LinearSearchTester LinearSearchTester

01: import java.util.Scanner;

02: 02:

03: /**

04: This program tests the linear search algorithm.

05: */

06: public class LinearSearchTester 06: public class LinearSearchTester 07: {

07: {

09: {

10: // Construct random array 10: // Construct random array 11:

11:

14: LinearSearcher searcher = new LinearSearcher(a);

15: 15:

16: Scanner in = new Scanner(System.in);

(61)

61 61

LinearSearchTester LinearSearchTester

18: boolean done = false;

19: while (!done) 19: while (!done) 20: {

20: {

21: System.out.print("Enter number to search for, 21: System.out.print("Enter number to search for,

-1 to quit: ");-1 to quit: ");

22: int n = in.nextInt();

23: if (n == -1) 23: if (n == -1) 24: done = true;

24: done = true;

25: else 25: else 26: { 26: {

27: int pos = searcher.search(n);

28: System.out.println("Found in position " + pos);

29: } 29: } 30: } 30: } 31: } 31: } 32: } 32: }

(62)

62 62

LinearSearchTester LinearSearchTester

46 99 45 57 64 95 81 69 11 97 6 85 61 88 29 65 83 88 45 88 46 99 45 57 64 95 81 69 11 97 6 85 61 88 29 65 83 88 45 88 Enter number to search for, -1 to quit: 11

Enter number to search for, -1 to quit: 11 Found in position 8

Found in position 8



Output: Output:

(63)

63 63

Ricerca Binaria Ricerca Binaria



Trova un valore in un array ordinato Trova un valore in un array ordinato

 Determinando ae il valore è presente Determinando ae il valore è presente nella prima o seconda metà

nella prima o seconda metà

 Ripetendo poi la ricerca in una delle due metàRipetendo poi la ricerca in una delle due metà

(64)

64 64

Ricerca Binaria Ricerca Binaria

15 ≠ 17: non c'è corrispondenza

(65)

65 65

BinarySearcher.java BinarySearcher.java

01: /**

02: A class for executing binary searches through an array.

03: */

04: public class BinarySearcher 04: public class BinarySearcher 05: {

05: { 06: /**

06: /**

07: Constructs a BinarySearcher.

08: @param anArray a sorted array of integers 08: @param anArray a sorted array of integers 09: */

09: */

10: public BinarySearcher(int[] anArray) 10: public BinarySearcher(int[] anArray) 11: {

11: {

12: a = anArray;

13: } 13: } 14:

14:

15: /**

16: Finds a value in a sorted array, using the binary 16: Finds a value in a sorted array, using the binary 17: search algorithm.

17: search algorithm.

18: @param v the value to search 18: @param v the value to search

19: @return the index at which the value occurs, or -1 19: @return the index at which the value occurs, or -1 20: if it does not occur in the array

20: if it does not occur in the array 21: */

21: */

(66)

66 66

BinarySearcher.java BinarySearcher.java

22: public int search(int v) 22: public int search(int v) 23: {

23: {

24: int low = 0;

25: int high = a.length - 1;

26: while (low <= high) 26: while (low <= high) 27: {

27: {

28: int mid = (low + high) / 2;

29: int diff = a[mid] - v;

30:

31: if (diff == 0) // a[mid] == v 31: if (diff == 0) // a[mid] == v 32: return mid;

32: return mid;

33: else if (diff < 0) // a[mid] < v 33: else if (diff < 0) // a[mid] < v 34: low = mid + 1;

34: low = mid + 1;

35: else 35: else

36: high = mid - 1;

37: } 37: }

(67)

67 67

Ricerca Binaria Ricerca Binaria



Contare il numero di visite per cercare in un array Contare il numero di visite per cercare in un array ordinato di dimensione n

ordinato di dimensione n

 Si visita un solo elemento (quello centrale) e poi si cerca Si visita un solo elemento (quello centrale) e poi si cerca nel sotto-array sinistro o in quello destro

nel sotto-array sinistro o in quello destro

 pertanto: pertanto: T(n) = T(n/2) + 1 T(n) = T(n/2) + 1



Se calcolo per il sotto-array di lunghezza pari a n/2, Se calcolo per il sotto-array di lunghezza pari a n/2, allora: T(n/2) = T(n/4) + 1

allora: T(n/2) = T(n/4) + 1



Sostituendo nell'equazione originaria: Sostituendo nell'equazione originaria:

T(n) = T(n/4) + 2 T(n) = T(n/4) + 2



This generalizes to: This generalizes to: T(n) = T(n/2 T(n) = T(n/2

^k^k

) + k ) + k

(68)

68 68

Ricerca Binaria Ricerca Binaria



Assumendo che n sia una potenza di 2, Assumendo che n sia una potenza di 2, ossia n = 2

ossia n = 2

^m^m

si può scrivere m = log

₂₂

(n) (n)



Allora: T(n) = 1 + log Allora: T(n) = 1 + log

₂₂

(n) (n)

