-
[분할정복] merge sort (합병 정렬)algoritm 2023. 3. 20. 23:49
분할정복 알고리즘
-> 큰 문제를 작은 문제들로 분할하고, 작은 문제들을 해결한 뒤에 이들의 해답을 이용하여, 문제의 최종 해답을 구하는 알고리즘이다.
그림처럼 분할 정복은 상단에서 분할하고, 중앙에서 정복하고 하단에서 조합하는 형태로 도식화된다. 분할 : 더 이상 분할할 수 없을때까지 동일한 유형의 여러 하위 문제로 나눈다.
정복 : 가장 작은 단위의 하위 문제를 재귀적으로 해결한다.
조합 : 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다.
대표적인 예로 Quick Sort , Merge Sort , Binary Search 등이 있다.
MergeSort
합병 정렬은 입력이 2개의 부분 문제로 분할되고, 부분 문제의 크기가 1/2로 감소하는 분할 정복 알고리즘이다.
1. 주어진 배열을 절반으로 분할하여 2개의 배열로 나눈다. (Divide)
2. 해당 부분 배열의 길이가 1이 아니라면 1번 과정을 되풀이 한다.
3. 인접한 두 배열을 정렬하여 합친다.(conqure)
1 , 2 번이 sort()메소드로 구현, 3 번은 merge()메소드로 구현.
배열을 정렬하는 sort 메소드
더이상 분할할 수 없을 때 까지 재귀적으로 호출하면서 배열을 쪼갠다.
public void sort(int[] arr) { // 입력된 배열이 null이거나 길이가 1 이하인 경우 정렬할 필요 없음 if (arr == null || arr.length <= 1) { return; } // 배열을 반으로 나누기 위한 중간값 계산 int mid = arr.length / 2; // 중간값을 기준으로 왼쪽과 오른쪽 배열 생성 int[] left = new int[mid]; int[] right = new int[arr.length - mid]; // 왼쪽 배열에 값을 할당 for (int i = 0; i < mid; i++) { left[i] = arr[i]; } // 오른쪽 배열에 값을 할당 for (int i = mid; i < arr.length; i++) { right[i - mid] = arr[i]; } // 왼쪽 배열과 오른쪽 배열을 재귀적으로 정렬 sort(left); sort(right); // 정렬된 왼쪽 배열과 오른쪽 배열을 병합 merge(left, right, arr); }
두 개의 배열을 오름차순으로 정렬하면서, 하나의 배열로 병합하는 merge메소드
// 두 개의 배열을 정렬하면서 하나의 배열로 병합하는 merge 메소드 private void merge(int[] left, int[] right, int[] arr) { int i = 0, j = 0, k = 0; while (i < left.length && j < right.length) { // 왼쪽 배열값 <= 오른쪽 배열 값, 왼쪽 배열의 값을 arr[]에 넣어줌 if (left[i] <= right[j]) { arr[k++] = left[i++]; } else { // 왼쪽 배열 값 > 오른쪽 배열 값 ,오른쪽 배열 값을 arr[]에 넣어줌 arr[k++] = right[j++]; } } // 왼쪽 배열이나 오른쪽 배열 중 하나가 먼저 정렬되었다면, 남은 값들을 마저 배열에 복사 while (i < left.length) { arr[k++] = left[i++]; } while (j < right.length) { arr[k++] = right[j++]; } }
참고문헌