Sortowanie przez scalanie w Javie

Co to jest sortowanie przez scalanie?

Sortowanie przez scalanie jest najpopularniejszym algorytmem sortowania danych przy użyciu techniki „ dziel i zwyciężaj ”. W tym algorytmie problem jest dzielony na podproblemy, które następnie po sortowaniu są łączone w całość. Załóżmy, że mamy listę nieposortowanych liczb, będącą wynikiem zajęć z określonego przedmiotu. Aby posortować je rosnąco, będziemy musieli umieścić je na liście zaczynając od najniższej do najwyższej. W tym algorytmie sortowania przez scalanie lista zostanie podzielona na mniejsze listy w celu posortowania ich w porządku rosnącym, a następnie wyniki zostaną scalone w celu lepszego zrozumienia. Sortowanie przez scalanie w Javie można wyjaśnić na przykładzie tablicy {6,9,8,2,4,1}, potraktuj to jako wynik testu klasy na 10. Tablica (wyników) będzie wielokrotnie dzielona na mniejsze kawałki, aż ich wielkość wyniesie 1. Następnie następuje proces łączenia przy jednoczesnym sortowaniu liczb. Dzięki temu otrzymamy wynik zaczynający się od najniższych ocen, a skończywszy na najwyższych otrzymanych ocenach. Tablica ta zostanie podzielona na dwie tablice, z których każda będzie zawierać 3 elementy, jak pokazano poniżej w kroku 2 , i dzieli się dalej, aż do osiągnięcia jedności w kroku 4 . Następnie algorytm Merge Sort zaczyna sortować liczby krok po kroku ( krok 5 ), a następnie łączy liczby w większą tablicę w krokach 6 i 7 .

Realizacja

W implementacji napiszemy kod algorytmu sortowania przez scalanie w Javie. Wymaganymi zmiennymi będą tablica wejściowa i długość tablicy. Te dwa parametry zostaną następnie użyte do wprowadzenia dalszych parametrów w celu utworzenia funkcji sortowania przez scalanie. Przyjrzyjmy się poniższemu fragmentowi, aby zrozumieć ogólne działanie algorytmu sortowania przez scalanie w Javie.

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

Najpierw poprzez warunek if Początek i Koniec służą do określenia środka. Następnie w następnym kroku tworzone są 2 nowe podtablice, zaczynając od początku do środka, a druga zaczynając od środka +1 do końca. Tablice te są dzielone, aż ich długość osiągnie 1, a następnie za pomocą funkcji scalania posortowane podtablice Beginning, Middle, Middle+1 i End są ponownie łączone w celu uzyskania rozwiązania.

Przykład

Poniższy kod w Javie wyjaśnia algorytm sortowania przez scalanie:

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");
    }
}

Wyjście

Wniosek

Sortowanie przez scalanie w Javie to prosty algorytm umożliwiający uzyskanie posortowanej listy z nieposortowanej listy liczb. Aby uzyskać dostęp do posortowanej tablicy z nieposortowanej tablicy, stosowana jest podstawowa metoda „ dziel i zwyciężaj ”.