Unisci ordinamento in Java

1. Introduzione

In questo tutorial, daremo uno sguardo all'algoritmo Merge Sort e alla sua implementazione in Java .

Il merge sort è una delle tecniche di ordinamento più efficienti e si basa sul paradigma "divide et impera".

2. L'algoritmo

Merge sort è un algoritmo di "divide et impera" in cui dividiamo prima il problema in sottoproblemi. Quando le soluzioni per i sottoproblemi sono pronte, le combiniamo insieme per ottenere la soluzione finale al problema.

Questo è uno degli algoritmi che possono essere facilmente implementati usando la ricorsione poiché ci occupiamo dei sottoproblemi piuttosto che del problema principale.

L'algoritmo può essere descritto come il seguente processo in 2 fasi:

  • Dividi: in questo passaggio, dividiamo l'array di input in 2 metà , il pivot è il punto medio dell'array. Questo passaggio viene eseguito in modo ricorsivo per tutti i mezzi array fino a quando non ci sono più mezzi array da dividere.
  • Conquista: in questo passaggio, ordiniamo e uniamo gli array divisi dal basso verso l'alto e otteniamo l'array ordinato.

Il diagramma seguente mostra il processo completo di ordinamento tramite unione per un array di esempio {10, 6, 8, 5, 7, 3, 4}.

Se diamo uno sguardo più da vicino al diagramma, possiamo vedere che l'array viene diviso ricorsivamente in due metà fino a quando la dimensione diventa 1. Una volta che la dimensione diventa 1, i processi di unione entrano in azione e iniziano a unire gli array durante l'ordinamento:

3. Implementazione

Per l'implementazione, scriveremo una funzione mergeSort che accetta l'array di input e la sua lunghezza come parametri. Questa sarà una funzione ricorsiva, quindi abbiamo bisogno della base e delle condizioni ricorsive.

La condizione di base controlla se la lunghezza dell'array è 1 e restituirà semplicemente. Per il resto dei casi, verrà eseguita la chiamata ricorsiva.

Per il caso ricorsivo, otteniamo l'indice centrale e creiamo due array temporanei l [] e r [] . La funzione mergeSort viene quindi chiamata in modo ricorsivo per entrambi i sotto-array:

public static void mergeSort(int[] a, int n) { if (n < 2) { return; } int mid = n / 2; int[] l = new int[mid]; int[] r = new int[n - mid]; for (int i = 0; i < mid; i++) { l[i] = a[i]; } for (int i = mid; i < n; i++) { r[i - mid] = a[i]; } mergeSort(l, mid); mergeSort(r, n - mid); merge(a, l, r, mid, n - mid); }

Chiamiamo quindi la funzione di unione che accetta l'input e sia i sotto-array che gli indici iniziale e finale di entrambi i sotto-array .

La funzione di unione confronta gli elementi di entrambi i sotto-array uno per uno e posiziona l'elemento più piccolo nell'array di input.

Quando raggiungiamo la fine di uno dei sotto-array, il resto degli elementi dell'altro array viene copiato nell'array di input dandoci così l'array finale ordinato:

public static void merge( int[] a, int[] l, int[] r, int left, int right) { int i = 0, j = 0, k = 0; while (i < left && j < right) { if (l[i] <= r[j]) { a[k++] = l[i++]; } else { a[k++] = r[j++]; } } while (i < left) { a[k++] = l[i++]; } while (j < right) { a[k++] = r[j++]; } } 

Lo unit test per il programma:

@Test public void positiveTest() { int[] actual = { 5, 1, 6, 2, 3, 4 }; int[] expected = { 1, 2, 3, 4, 5, 6 }; MergeSort.mergeSort(actual, actual.length); assertArrayEquals(expected, actual); }

4. Complessità

Poiché l'ordinamento di unione è un algoritmo ricorsivo, la complessità temporale può essere espressa come la seguente relazione ricorsiva:

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

2T (n / 2) corrisponde al tempo richiesto per ordinare i sotto-array e il tempo O (n) per unire l'intero array.

Una volta risolto, la complessità temporale arriverà a O (nLogn).

Questo è vero per il caso peggiore, medio e migliore poiché divide sempre l'array in due e quindi si fonde.

La complessità spaziale dell'algoritmo è O (n) poiché stiamo creando array temporanei in ogni chiamata ricorsiva.

5. conclusione

In questo breve tutorial, abbiamo visto il funzionamento dell'algoritmo di ordinamento di unione e come possiamo implementarlo in Java.

L'intero codice funzionante è disponibile su GitHub.