import java.util.Arrays; /** * Questa classe confronto le prestazioni di vari algoritmi di ordinamento: selection sort, merge * sort, e l'algoritmo di ordinamento integrato in Java (il dual-pivot quicksort). */ public class ConfrontoAlgoritmiOrdinamento { /** * Copia gli elmenti dell'array "a" negli array "first" e "second". I primi elementi vengono * copiati in "first", quelli che avanzano in "second". Si asssume che la la lunghezza di "a" * sia la somma delle lunghezza di first e di second. * * La complessità in tempo di split è O(n), dove n è la lunghezza di "a". La complessità in * spazio è O(1), perché utilizza solo un numero costante di celle di memoria per la variabile * i. */ public static void split(int[] a, int[] first, int[] second) { // Copia gli elementi di a in first, finché c'è spazio for (int i = 0; i < first.length; i++) { first[i] = a[i]; } // Copia i restanti elementi in second for (int i = first.length; i < a.length; i++) { // notare che i indica la posizione dell'elemento a da copiare, ma l'elemento di a in // posizione first.length va copiato nella posizione 0 di second. Questo spiega la // differenza "i - first.length". second[i - first.length] = a[i]; } } /** * Dati i due array ordinati "first" e "second", questo metodo copia i valori di entrambi in * "a", mantenendo l'ordine complessivo. Ad esempio, se first = { 1, 10, 15 } e second = { 2, 9, * 12, 13 }, l'array a verrà riempito con { 1, 2, 9, 10, 12, 13, 15 }. Si asssume che la * lunghezza di a sia la somma delle lunghezza di first e di second. * * La complessità in tempo di merge è O(n), dove n è la lunghezza di "a". La complessità in * spazio è O(1), perché utilizza solo un numero costante di celle di memoria per le variabili i * e j. */ public static void merge(int[] a, int[] first, int[] second) { // i punta al prossimo elemento di first da copiare in a // j punta al prossimo elemento di second da copiare in a int i = 0, j = 0; // cicla finché sia in first che in second ci sono elementi da copiare while (i < first.length && j < second.length) { // se l'elemento da copiare di first è più piccolo di quello di second, copia l'elemento // di first, altrimenti copia l'elemento di second if (first[i] < second[j]) { // copia il prossimo elemento di first nella giusta posizione di a a[i + j] = first[i]; // avanza alla successiva posizione di first i += 1; } else { // copia il prossimo elemento di second nella giusta posizione di a a[i + j] = second[j]; // avanza alla successiva posizione di second j += 1; } } // A questo punto, potrebbero essere rimasti elementi da first o da second non copiati (ma // non da entrambi, uno dei due array sarà sicuramente terminato). Prima di tutto, copio // gli eventuali elementi rimasti in first. while (i < first.length) { a[i + j] = first[i]; i += 1; } // Adesso copio gli eventuali elementi rimasti in second. while (j < second.length) { a[i + j] = second[j]; j += 1; } } /** * Dato un array a, ordina gli elementi dal più piccolo al più grade. Utilizza l'algoritmo noto * come merge sort. * * La complessità in tempo di mergeSort è O(n*log(n)), dove n è la lunghezza di "a". La * complessità in spazio è anch'essa O(n*log n), a causa dell'allocazione dei vettori first e * second. * * Capire che è O(n*log n) non è banalissimo, ma dovrebbe essere evidente che non è O(1) perché * solo la prima chiamata di mergeSort alloca due array (first e second) la cui somma delle * lunghezze è n. */ public static void mergeSort(int[] a) { if (a.length <= 1) // CASO BASE: se l'array ha uno o due elementi, è sicuramente già ordinato return; else { // CASO INDUTTIVO // Calcolo la metà (eventualmente approssimata) della lunghezza di a int half = a.length / 2; // Ceo due array destinati a contenere la prima e la seconda parte di a. Se a.length è // pari, i due array hanno esattamente la stessa lunghezza (la metà di a.length) // altrimenti il secondo avrà un elemento in più del primo (provare con a.length = 8 e // con a.length = 9 per convincersi). int[] first = new int[half]; int[] second = new int[a.length - half]; // Usando il metodo split, divide a tra gli array first e second split(a, first, second); // Prima chiamata ricorsiva: ordina first mergeSort(first); // Seconda chiamata ricorsiva: ordina second mergeSort(second); // Ricopia gli array ordinati first e second in a, mantenendo l'ordine merge(a, first, second); } } /** * Crea un array lungo length formato da numeri casuali. I numeri saranno interi tra 0 e max-1. */ public static int[] createRandom(int length, int max) { // Creo l'array lungo length inizializzato con i valori di defaults int[] a = new int[length]; // Ciclo per tutte le posizioni dell'array a for (int i = 0; i < length; i++) { // Metto nella posizione i un numero casuale a[i] = (int) (Math.random() * max); } return a; } /** * Dato un array a, ordina gli elementi dal più piccolo al più grade. Utilizza l'algoritmo noto * come Selection Sort. * * La complessità in tempo di selectionSort è O(n*n), dati i due for annidati. La complessità in * spazio è O(1), visto che la quantità di memoria utilizzata è fissa (lo spazio per le * variabili i, j e tmp). */ public static void selectionSort(int[] a) { // Il selection sort mette a posto nell'array un elemento alla volta. Il ciclo // esterno indica quale elemento si mette a posto. for (int i = 0; i < a.length; i++) { // Quando il programma è in questo punto, gli elementi da a[0] ad a[i-1] sono già // ordinati, correttamente. Rimane da ordinare gli elementi da a[i] in poi. // Per prima cosa determiniamo la posizione dell'elemento minimo da a[i] in pos. int posmin = i; for (int j = i + 1; j < a.length; j++) { if (a[j] < a[posmin]) posmin = j; } // Scambiamo l'elemento minimo con l'elemento in posizione i int tmp = a[i]; a[i] = a[posmin]; a[posmin] = tmp; // A questo punto abbiamo sistemato l'elemento in posizione i e possiamo ricominciare il // ciclo in modo da ordinare quello in posizione i+1. } } /** * Questo metodo esegue il Runnable passato come argomento, misurandone il tempo di esecuzione. * Come funzioni non fa parte del programma del corso. */ public static void timeIt(Runnable f) { try { long startTime = System.nanoTime(); f.run(); long endTime = System.nanoTime(); double time = (endTime - startTime) * 1.0 / 1_000_000; System.out.printf("Tempo di esecuzione: %.3f millisecondi\n", time); } catch (IllegalAccessError e) { System.out.println("Si è verificato un errore"); } } public static void main(String[] args) { int[] x = createRandom(50_000, 100_000); if (x.length < 20) System.out.println("Array prima dell'ordinamento: " + Arrays.toString(x)); int[] y1 = x.clone(); System.out.println("Inizio selectionsort"); timeIt(() -> selectionSort(y1)); System.out.println("Fine selectionsort"); if (x.length < 20) System.out.println("Array dopo l'ordinamento: " + Arrays.toString(y1)); System.out.println("-------------------------"); int[] y3 = x.clone(); System.out.println("Algoritmo di ordinamento integrato in java"); timeIt(() -> Arrays.sort(y3)); System.out.println("Fine ordinamento"); if (x.length < 20) System.out.println("Array dopo l'ordinamento: " + Arrays.toString(y3)); int[] y2 = x.clone(); System.out.println("Inizio mergesort"); timeIt(() -> mergeSort(y2)); System.out.println("Fine mergesort"); if (x.length < 20) System.out.println("Array dopo l'ordinamento: " + Arrays.toString(y2)); System.out.println("-------------------------"); } }