Java의 병합 정렬

병합 정렬이란 무엇입니까?

병합 정렬은 " 분할 및 정복 " 기술을 사용하여 데이터를 정렬하는 가장 일반적인 알고리즘입니다. 이 알고리즘에서는 문제를 하위 문제로 나눈 다음 정렬한 후 병합합니다. 특정 주제에 대한 수업 결과인 정렬되지 않은 숫자 목록이 있다고 가정해 보겠습니다. 오름차순으로 정렬하려면 낮은 것부터 높은 것 순으로 목록에 배치해야 합니다. 이 병합 정렬 알고리즘에서는 목록을 더 작은 목록으로 나누어 오름차순으로 정렬한 다음 더 나은 이해를 위해 결과를 병합합니다. Java의 병합 정렬은 배열 {6,9,8,2,4,1}의 예를 통해 설명할 수 있으며 이를 10개 중 클래스 테스트의 결과로 간주합니다. (결과의) 배열은 반복적으로 나누어집니다. 크기가 1이 될 때까지 더 작은 덩어리로 나눕니다. 그런 다음 숫자를 동시에 정렬하면서 병합 프로세스가 수행됩니다. 이렇게 하면 가장 낮은 점수부터 시작하여 가장 높은 점수까지 받은 결과가 제공됩니다. 이 배열은 아래 2단계 에서 볼 수 있듯이 각각 3개의 요소를 포함하는 두 개의 배열로 나누어지며 4단계 에서 일치할 때까지 계속 나누어집니다 . 그런 다음 병합 정렬 알고리즘은 한 번에 한 단계씩 숫자를 정렬하기 시작하고( 5단계 ) 6단계와 7단계 에서 숫자를 더 큰 배열로 병합합니다 .

구현

구현에서는 Java로 병합 정렬 알고리즘에 대한 코드를 작성합니다. 필요한 변수는 입력 배열과 배열 길이입니다. 이 두 매개변수는 병합 정렬 기능을 생성하기 위한 추가 매개변수를 도입하는 데에도 사용됩니다. 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

먼저 if 조건을 통해 Beginning과 End를 사용하여 중간을 결정합니다. 그런 다음 다음 단계에서는 2개의 새로운 하위 배열이 시작부터 중간까지 생성되고 다른 하나는 중간 +1부터 끝까지 생성됩니다. 이 배열을 길이가 1이 될 때까지 나눈 후 Merge 함수를 통해 정렬된 하위 배열인 Beginning, Middle, Middle+1 및 End를 모두 다시 병합하여 해를 얻습니다.

예

다음 Java 코드는 병합 정렬 알고리즘을 설명합니다.

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

산출

결론

Java의 병합 정렬은 정렬되지 않은 숫자 목록에서 정렬된 목록을 얻는 간단한 알고리즘입니다. 정렬되지 않은 배열에서 정렬된 배열에 액세스하려면 ' 분할 및 정복 ' 이라는 기본 방법이 적용됩니다.