병합 정렬이란 무엇입니까?
병합 정렬은 " 분할 및 정복 " 기술을 사용하여 데이터를 정렬하는 가장 일반적인 알고리즘입니다. 이 알고리즘에서는 문제를 하위 문제로 나눈 다음 정렬한 후 병합합니다. 특정 주제에 대한 수업 결과인 정렬되지 않은 숫자 목록이 있다고 가정해 보겠습니다. 오름차순으로 정렬하려면 낮은 것부터 높은 것 순으로 목록에 배치해야 합니다. 이 병합 정렬 알고리즘에서는 목록을 더 작은 목록으로 나누어 오름차순으로 정렬한 다음 더 나은 이해를 위해 결과를 병합합니다. 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예
다음 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");
}
}산출
원래 배열 [6, 9, 8, 2, 4, 1] 병합 정렬 후 [1, 2, 4, 6, 8, 9]
GO TO FULL VERSION