합병 정렬(Merge Sort)
은 분할 정복(Divide and Conquer)
방식으로 배열을 분할하고, 최종적으로 분할된 배열에서 대소 비교를 이룬 뒤 다시 배열을 합치는 정렬 방식이다.
배열을 중간 인덱스를 기준으로 좌, 우로 나눈다. 이 방식을 지속적으로 반복하며 최종적으로 Partition에 2개의 요소가 남을 때까지 반복한다. 아래 그림을 참고하자.
위의 그림에서 가운데 부분을 보자. 가운데 부분에서는 바로 윗 단계의 2개의 요소로 구성된 Partition 에서 대소 비교를 진행하고, 그 다음부터 합병을 진행하게 되는 것이다.
따라서, 지속적으로 배열을 분할하다가 특정 지점에서 대소 비교를 이루고 배열을 합병하면 되는 것이다. 바로 코드를 보도록 한다.
public static void main(String[] args) {
System.out.println("병합/합병 정렬을 실시합니다.");
int[] arr = {78, 33, 95, 18, 45, 91, 58, 23, 75, 69, 78, 52, 38, 98, 68, 90, 36, 19};
int[] temp = new int[arr.length];
MergeSort(arr, temp, 0, arr.length - 1);
for(int i : arr) System.out.print(i + " ");
}
public static void MergeSort(int[] arr, int[] temp, int low, int high) {
if(low < high) {
int mid = (high + low) / 2;
MergeSort(arr, temp, low, mid);
MergeSort(arr, temp, mid + 1, high);
// 위 2개의 재귀함수 호출로 인해 배열의 부분이 지속적으로 분할된다.
// 배열의 분열을 마쳤으므로 정렬을 시작하도록 한다.
Merge(arr, temp, low, mid, high);
}
}
public static void Merge(int[] arr, int[] temp, int low, int mid, int high) {
for(int i = low; i <= high; i++) // 임시 배열에 원래 배열을 필요한 만큼 복사해 준다.
temp[i] = arr[i];
int part1 = low; // 좌측 배열의 첫 번째 인덱스
int part2 = mid + 1; // 우측 배열의 첫 번째 인덱스
int index = low; // 양쪽 배열에서 작은 값을 복사할 때마다 결과 배열에 어디에 저장할지 나타내는 변수
while(part1 <= mid && part2 <= high) { // 양쪽 배열을 끝까지 돌도록 한다.
if(temp[part1] < temp[part2]) { // 앞의 배열의 원소가 작은 경우
arr[index] = temp[part1];
part1++;
}
else { // 뒤의 배열의 원소가 작은 경우
arr[index] = temp[part2];
part2++;
}
index++;
}
// 만약, 주어진 배열이 홀수개이거나 한 경우 좌측 배열에서 하나는 끝났는데 다른 하나는 끝나지 않았을 것이다.
// 띠리서, 배열에 값을 다 넣어주기 위해서 아래의 코드를 실행한다.
// 참고로 위 while 반복문이 끝나면 최종 인덱스는 index 이다.
for(int i = 0; i <= mid - part1; i++)
arr[index + i] = temp[part1 + i];
}
병합/합병 정렬을 실시합니다.
18 19 23 33 36 38 45 52 58 68 69 75 78 78 90 91 95 98
구현 코드 및 실행 결과는 위 그림과 같다.
이러한 합병 정렬
은 시간 복잡도를 항상 O(nlogn)
으로 갖게 된다.