Hợp nhất sắp xếp trong Java

Sắp xếp hợp nhất là gì?

Sắp xếp Hợp nhất là đại số phổ biến nhất để sắp xếp dữ liệu bằng kỹ thuật “ chia để trị ”. Trong thuật toán này, bài toán được chia thành các bài toán con và sau khi sắp xếp chúng được hợp nhất lại với nhau. Giả sử chúng ta có một danh sách các số chưa được sắp xếp, kết quả của một lớp cho một chủ đề nhất định. Để sắp xếp chúng theo thứ tự tăng dần, chúng ta sẽ cần đặt chúng vào danh sách bắt đầu từ thấp đến cao. Trong thuật toán Merge Sort này, danh sách sẽ được chia thành các danh sách nhỏ hơn để sắp xếp theo thứ tự tăng dần sau đó sẽ gộp các kết quả lại để hiểu rõ hơn. Hợp nhất Sắp xếp trong Java có thể được giải thích thông qua ví dụ về mảng {6,9,8,2,4,1}, coi đó là kết quả của một bài kiểm tra lớp trên 10. Mảng (kết quả) sẽ được chia đi nhiều lần thành các phần nhỏ hơn cho đến khi kích thước của chúng bằng 1. Sau đó, quá trình hợp nhất diễn ra đồng thời sắp xếp các số. Điều này sẽ cung cấp cho chúng tôi một kết quả bắt đầu từ điểm thấp nhất đến điểm cao nhất nhận được. Mảng này sẽ được chia thành hai mảng, mỗi mảng chứa 3 phần tử như được hiển thị bên dưới trong bước 2 và nó tiếp tục phân chia cho đến khi đạt được sự thống nhất ở bước 4 . Sau đó, thuật toán Sắp xếp Hợp nhất bắt đầu sắp xếp các số từng bước một ( bước 5 ) rồi hợp nhất các số thành một mảng lớn hơn ở bước 6 & 7 .

Thực hiện

Trong quá trình triển khai, chúng ta sẽ viết mã cho thuật toán sắp xếp hợp nhất trong Java. Các biến được yêu cầu sẽ là mảng đầu vào và độ dài của mảng. Hai tham số này sẽ tiếp tục được sử dụng để giới thiệu các tham số khác nhằm tạo ra hàm sắp xếp hợp nhất. Chúng ta hãy xem đoạn mã bên dưới để hiểu hoạt động chung của Thuật toán Sắp xếp Hợp nhất trong 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

Đầu tiên cho đến điều kiện if Bắt đầu và Kết thúc được sử dụng để xác định Phần giữa. Sau đó, trong bước tiếp theo, 2 mảng con mới được tạo bắt đầu từ Đầu đến Giữa và mảng con còn lại bắt đầu từ Giữa +1 đến Cuối. Các mảng này được chia cho đến khi độ dài của chúng bằng 1 và sau đó thông qua Hàm Hợp nhất, các mảng con được sắp xếp Bắt đầu, Giữa, Giữa+1 và Cuối đều được hợp nhất lại để thu được giải pháp.

Ví dụ

Đoạn mã sau trong Java giải thích thuật toán sắp xếp hợp nhất:

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

đầu ra

Phần kết luận

Hợp nhất Sắp xếp trong Java là một thuật toán đơn giản để thu được danh sách được sắp xếp từ danh sách các số chưa được sắp xếp. Phương pháp cơ bản ' phân chia và chinh phục ' được áp dụng để truy cập mảng đã sắp xếp từ một mảng chưa sắp xếp.