import java.util.Arrays; public class P2Algorithms2 { /** * Trova la posizione di x nel vettore ORDINATO a. Versione iterativa. */ public static int binarySearchIterative(int[] a, int x) { // min contiene la posizione del primo elemento di a dove cercare x int min = 0; // max conrtiene la posizione dell'ultimi elemento di a dove cercare x int max = a.length - 1; // cicla finché c'è almento un elemento tra min e max while (min <= max) { // calcola la posizione centrale tra min e max int pos = (min + max) / 2; // confronta a[pos] con x if (a[pos] == x) // x trovato! return pos; else if (x > a[pos]) // x, se c'è, si trova prima di pos max = pos - 1; else // x, se c'è, si trova dopo pos min = pos + 1; } // se siamo arrivati qui vuol dire che non abbiamo trovato x return -1; } /** * Trova la posizione di x nel vettore ORDINATO a, ristretto alle posizioni tr min e max. * Versione ricorsiva. */ public static int binarySearch(int[] a, int x, int min, int max) { // controlla se c'è almeno un elemento tra min e max if (min <= max) { // calcola la posizione centrale int pos = (min + max) / 2; // confronta a[pos] con x if (x == a[pos]) // x trovato! return pos; else if (x > a[pos]) // x, se c'è, si trova tra pos+1 e max return binarySearch(a, x, pos + 1, max); else // x, se c'è, si trova tra min e pos-1 return binarySearch(a, x, min, pos - 1); } // se siamo arrivato qui vuol dire che non c'è nessun elemento tra min // e max, e quindi sicuramente non c'è x return -1; } /** * Trova la posizione di x nel vettore ORDINATO a. Richiama semplicemente la versione di * binarySearch con 4 parametri, specificando i valori iniziali dei parametri min e max. */ public static int binarySearch(int[] a, int x) { return binarySearch(a, x, 0, a.length - 1); } /** * Copia gli elmenti dell'array a negli array first e secondi. 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. */ 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 la * lunghezza di a sia la somma delle lunghezza di first e di second. */ 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. */ 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. */ 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(100, 100_000); System.out.println("Inizio ordinamento"); System.out.println("Array prima dell'ordinamento: " + Arrays.toString(x)); timeIt(() -> mergeSort(x)); System.out.println("Fine ordinamento"); System.out.println("Array dopo l'ordinamento: " + Arrays.toString(x)); } }