Unisci ordinamento in Java

Cos'è l'ordinamento unito?

Il Merge Sort è l’algoritmo più comune per l’ordinamento dei dati utilizzando la tecnica “ dividi et impera ”. In questo algoritmo il problema viene diviso in sottoproblemi che, dopo essere stati ordinati, vengono uniti insieme. Supponiamo di avere un elenco di numeri non ordinati, risultato di una classe per un determinato argomento. Per ordinarli in ordine crescente dovremo inserirli in un elenco partendo dal basso verso l'alto. In questo algoritmo Merge Sort, l'elenco verrà diviso in elenchi più piccoli per ordinarli in ordine crescente e quindi unirà i risultati per una migliore comprensione. Merge Sort in Java può essere spiegato attraverso un esempio di un array {6,9,8,2,4,1}, consideralo come il risultato di un test di classe su 10. L'array (dei risultati) verrà diviso ripetutamente in pezzi più piccoli finché la loro dimensione non diventa 1. Quindi avviene il processo di fusione ordinando i numeri simultaneamente. Questo ci fornirà un risultato che inizia con il punteggio più basso fino al punteggio più alto ricevuto. Questo array sarà diviso in due array che conterranno 3 elementi ciascuno come mostrato di seguito nel passaggio 2 e continuerà a dividersi fino a raggiungere l'unità nel passaggio 4 . Quindi l'algoritmo Merge Sort inizia a ordinare i numeri un passo alla volta ( passo 5 ) e poi unisce i numeri in un array più grande nei passaggi 6 e 7 .

Implementazione

Nell'implementazione scriveremo il codice per l'algoritmo di merge sort in Java. Le variabili richieste saranno l'array di input e la lunghezza dell'array. Questi due parametri verranno inoltre utilizzati per introdurre ulteriori parametri per creare la funzione di ordinamento di unione. Diamo un'occhiata allo snippet seguente per comprendere il funzionamento generale dell'algoritmo Merge Sort in Java.

Merge_Sort_Algo (Array, Beginning, End)
/** Three parameters required for the Merge Sort Algorithm
 * Array = values of the array
 * Beginning = the starting element of the array
 * End = the ending element of the array*/

if (Beginning < End) // condition check Beginning must be less than End

set Middle = (Beginning + End) / 2 // Assigning Middle to the array

Merge_Sort_Algo (Array, Beginning, Middle) /** Sorting and merging of elements from Beginning to the Middle */

Merge_Sort_Algo (Array, Middle +1, End) /** Sorting and merging of elements from Middle to the End */

Merge (Array, Beginning, Middle, End) // Merging both the sorted arrays

end of if

End Merge_Sort_Algo

Dall'inizio alla condizione if, l'inizio e la fine vengono utilizzati per determinare il centro. Quindi nel passaggio successivo vengono creati 2 nuovi sottoarray partendo dall'inizio fino al centro e l'altro partendo dal centro +1 fino alla fine. Questi array vengono divisi fino a quando la loro lunghezza diventa 1 e quindi tramite la funzione Merge i sottoarray ordinati Inizio, Medio, Medio+1 e Fine vengono tutti riuniti per acquisire la soluzione.

Esempio

Il seguente codice in Java spiega l'algoritmo di ordinamento di unione:

import java.util.Arrays;

class HelloWorld {

    public static void merge(

  int[] array, int[] new_array_1, int[] new_array_2, int left, int right) {
   // defining parameters

    int i = 0, j = 0, k = 0;

    while (i < left && j < right) {  // conditions for merging

        if (new_array_1[i] <= new_array_2[j]) {
            array[k++] = new_array_1[i++];
        }
        else {
            array[k++] = new_array_2[j++];
        }
    }

    while (i < left) {
        array[k++] = new_array_1[i++];
    }

    while (j < right) {
        array[k++] = new_array_2[j++];
    }
}

    public static void mergeSort(int[] array, int length) { /** required parameters */
	if (length < 2) {  //condition for the length of array
    	return;
	}

	int middle = length / 2;  // defining new parameter middle

	int [ ] new_array_1 = new int [middle]; /** defining the new first array after division */
	int [ ] new_array_2 = new int [length - middle]; /** defining the new second array */


	for (int i = 0; i < middle; i++) { /**applying condition for sorting of new array 1 */
    	new_array_1 [ i ] = array [ i ];
	}

	for (int i = middle; i < length ; i++) { /**applying condition for sorting of new array 2 */
    	new_array_2 [ i - middle] = array [ i ];
	}

	mergeSort (new_array_1, middle); /** calling merge sort function for new array 1 */
	mergeSort (new_array_2, length - middle); /** calling merge sort function for new array 2 */


	merge(array, new_array_1, new_array_2, middle, length - middle); /** calling function for merging of new array 1 and new array 2 */
}


    public static void main(String[] args) {

        int [ ] testScores = {6,9,8,2,4,1};
        int size = testScores.length;

        System.out.println("Original Array " + Arrays.toString(testScores) + "\n");

        mergeSort(testScores, size);

        System.out.println("After Merge Sort " + Arrays.toString(testScores) + "\n");
    }
}

Produzione

Conclusione

Merge Sort in Java è un semplice algoritmo per acquisire un elenco ordinato da un elenco di numeri non ordinato. Il metodo di base " divide et impera " viene applicato per accedere all'array ordinato da un array non ordinato.