Corsi precedenti

Sesta (ed ultima) Esercitazione in Laboratorio

In questa esercitazione ci proponiamo di approfondire la conoscenza degli algoritmi di ordinamento; in particolare

• implementeremo due algoritmi di ordinamento, insertion sort e merge sort;
• analizzeremo sperimentalmente le prestazioni dei due algoritmi, ordinando array con caratteristiche diverse.

Implementazione

Implementare i due metodi seguenti:

public static void insertionSort(int[] arr) {...}
public static void mergeSort(int[] arr) {...}

Si suggerisce di non consultare le dispense del corso; ricordare le idee alla base dei due algoritmi di ordinamento e ricavarne il codice.

Testare il corretto funzionamento dei metodi implementati.

Analisi sperimentale delle prestazioni

Insertion sort ha costo nel caso peggiore, ma trae vantaggio da input parzialmente ordinati: se l’input è completamente ordinato, oppure è ordinato a meno di un numero costante di scambi, il costo diviene lineare. Merge sort ha costo , indipendentemente dall’ordinamento dell’input.

Vogliamo analizzare sperimentalmente le prestazioni dei due algoritmi in presenza di input parzialmente ordinati e di input completamente casuali. Per generare input parzialmente ordinati, realizzare il seguente metodo:

public static int[] generaArrayConScambi(int n, int s) {...}

che restituisce un array di n elementi, ordinato a meno di s scambi. In altre parole, il metodo inizialmente genera un array del tutto ordinato (per esempio l’array {1, 2, 3, ..., n}) e successivamente effettua s volte uno scambio fra due elementi dell’array scelti a caso.

Realizzare inoltre un metodo che generi array casuali, con valori compresi fra 0 e Integer.MAX_VALUE:

public static int[] generaArrayRandom(int n) {...}

Consideriamo diverse dimensioni dell’input; per esempio, prendiamo in . Per ciascuna dimensione, analizziamo le prestazioni di entrambi gli algoritmi con

• input casuale;
• input parzialmente ordinato, con scambi, al variare di .

Ci aspettiamo che per piccoli valori di insertion sort sia più efficiente di merge sort; al crescere di merge sort diventa via via più efficiente, fino a superare l’efficienza dell’insertion sort. Individuare sperimentalmente, per ogni considerato, il valore di per cui merge sort diventa più efficiente di insertion sort.

Suggerimenti e guida per lo svolgimento dell’analisi

• per misurare il tempo di esecuzione di un algoritmo si suggerisce di usare il metodo System.currentTimeMillis(): invocarlo subito prima e subito dopo l’esecuzione dell’algoritmo, e calcolare la differenza dei tempi riportati;
• per valori piccoli di il metodo da analizzare potrebbe essere troppo veloce per essere misurabile. In tal caso misurare il costo di esecuzioni consecutive del metodo, per un opportuno valore di . Per esempio, si suggerisce di scrivere un metodo public static double runMergeSort(int[] arr, int k), che esegue k volte il metodo mergeSort(b), dove b è una copia di arr (ogni volta occorre costruire una copia dell’array da ordinare, perché mergeSort fa side effect). Il metodo restituisce il tempo medio di esecuzione, espresso in millisecondi.
• scegliere valori di in funzione del valore scelto di . Si suggerisce di compilare una tabella simile alla seguente; i valori mostrati nella tabella sono indicativi, e sono frutto degli esperimenti compiuti dal tutore:
  

  n e k

  Algoritmo

  s = 40

  s = 50

  s = 60

  s = 70

  s = 80

  s = 90

  s = 100

  s = 110

  s = 120

  s = 130

  s = 140

  Random

  n = 100 (k = 10.000)

  IS

  MS

  n = 1.000 (k = 1.000)

  IS

  MS

  n = 10.000 (k = 200)

  IS

  MS

  n = 100.000 (k = 20)

  IS

  MS

  n = 1.000.000 (k=2)

  IS

  MS

Commenti dei visitatori

Accedi per lasciare commenti.