병합 정렬 (Merge Sort)
병합 정렬은 분할 정복 알고리즘으로 평균적으로 효율적인 정렬 방법입니다.
병합 정렬은 배열을 더 이상 나눌 수 없을 때까지 반으로 나눕니다. 나눈 배열을 정렬하고 병합하면서 전체 배열의 정렬을 완성합니다.
시간 복잡도 : O(n log n)
반으로 나누면서 진행하기 때문에 시간 복잡도는 O(n log n)입니다. 최악의 상황에서도 O(n log n)입니다.
평균적인 속도는 퀵 정렬 > 힙 정렬 > 병합 정렬 입니다.
장점
- 안정적인 정렬 : 같은 값의 요소가 정렬 후에도 순서를 유지합니다.
- 일정한 시간 복잡도 : 모든 경우에 대해 O(n log n)입니다. 데이터에 관계없이 일정한 성능을 보장합니다.
- 대규모 데이터에 효율적 : 크기가 큰 데이터에서 효율적입니다.
단점
- 추가적인 메모리 필요 : 추가 배열을 사용하기 때문에 O(n)의 공간이 필요합니다.
- 비교적 느린 속도 : 병합 정렬은 퀵 정렬 같은 다른 정렬 알고리즘에 비해 상대적으로 느린 편입니다. 작은 데이터 세트에 대해 더 효율적인 알고리즘이 있습니다.
이러한 장단점을 고려하여, 병합 정렬은 메모리 사용량이 문제가 되지 않고, 안정적인 정렬이 필요하며 데이커 크기가 큰 경우에 적합한 알고리즘 입니다.
동작 과정
1. 분할 : 배열을 계속 반으로 나눕니다. 분할 과정은 부분 리스트가 하나의 요소만 가질 때까지 계속됩니다. 하나의 요소를 가진 리스트는 정렬되었다고 간주합니다.
2. 결합 정렬 : 분할된 배열을 다시 병합하면서 정렬합니다. 두 개의 배열에서 요소들을 올바른 순서로 병합하여 배열을 정렬합니다. 전체 배열로 합쳐질 때까지 계속합니다.
즉 요소가 하나가 될때까지 반씩 분할하는데 필요한 단계의 수는 O(log n)입니다.
병합 단계에서각 단계에서 모든 요소를 한 번씩 비교하여 O(n)이 됩니다.
총 O(log n) 단계가 있고 각 단계마다 비교하면 O(n)이 걸리므로 전체 시간 복잡도는 O(n log n)이 됩니다.
예시
원본 배열 : [38, 27, 43, 3, 9, 82, 19]
분할 단계 : 배열을 반으로 계속 나누어 하나의 요소가 될 때까지 나눕니다.
[38, 27, 43, 3] [9, 82, 19]
[38, 27] [43, 3] [9, 82] [19]
[38] [27] [43] [3] [9] [82] [19]
병합 정렬 : 인접한 두 배열의 정렬하면서 병합합니다. 이 때, 각 첫 번째 자리의 비교하여 낮은 숫자부터 앞으로 배치합니다.
[38] [27]을 정렬하면서 병합
[38]
[27]
[]
각 배열의 첫 번째 숫자 중 작은 것을 먼저 나오게 합니다. 38과 27중 27이 나옵니다.
[38]
[]
[27]
배열에 더 이상 없으므로 38이 나옵니다.
[]
[]
[27, 38]
총 배열은 다음과 같이 됩니다.
[27, 38] [43, 3] [9, 82] [19]
[43] [3] 도 정렬하면서 병합하면 [3, 43]이 됩니다.
[27, 38] [3, 43] 정렬하면서 병합
[27, 38]
[3, 43]
결과 배열 : []
두 개의 배열에서 첫 번째 숫자를 비교하합니다. 3이 더 작으므로 3이 먼저 나옵니다.
[27, 38]
[43]
결과 배열 : [3]
첫 번째 숫자를 비교하면 27이 작으므로 27이 나옵니다.
[38]
[43]
결과 배열 : [3, 27]
다음 두 배열의 첫 번째 숫자를 비교하면 38이 작으므로 38이 나옵니다.
[]
[43]
결과 배열 : [3, 27, 38]
위의 배열이 비었으므로 나머지 배열의 값들을 넣습니다.
[]
[]
결과 배열 : [3, 27, 38, 43]
이런 식으로 부분적으로 정렬하면서 병합하여 최종적으로 정렬된 배열을 완성합니다.
최종 정렬 배열 : [3, 9, 19, 27, 38, 43, 82]
Java 구현 코드
/*
병합 정렬
참고 영상 : https://www.youtube.com/watch?v=QAyl79dCO_k
*/
public class MergeSort {
public static void main(String[] args) {
int[] array = {38, 27, 43, 3, 9, 82, 19};
printArray(array);
mergeSort(array);
printArray(array);
}
// 병합 정렬 시작
public static void mergeSort(int[] array) {
int[] temp = new int[array.length];
mergeSort(array, temp, 0, array.length - 1);
}
// 병합 정렬 재귀
public static void mergeSort(int[] array, int[] temp, int start, int end) {
if(start < end) {
// 배열을 반으로 나눔
int mid = (start + end) / 2;
// 재귀를 통해 정렬
mergeSort(array, temp, start, mid);
mergeSort(array, temp, mid+1, end);
// 정렬된 왼쪽과 오른쪽을 합치는 함수
merge(array, temp, start, mid, end);
}
}
// 정렬된 왼쪽과 오른쪽을 합치는 함수
public static void merge(int[] array, int[] temp, int start, int mid, int end) {
// 임시 저장소에 왼쪽과 오른쪽을 저장
for(int i = start; i <= end; i++) {
temp[i] = array[i];
}
int part1 = start; // 왼쪽의 시작지점
int part2 = mid + 1; // 오른쪽의 시작지점
int index = start; // 결과 배열에 저장될 인덱스
// 왼쪽과 오른쪽을 비교해서 작은 것부터 결과 인덱스에 저장
while(part1 <= mid && part2 <= end) {
// 왼쪽이 작을 경우
if(temp[part1] <= temp[part2]) {
array[index] = temp[part1];
part1++;
}
// 오른쪽이 작을 경우
else {
array[index] = temp[part2];
part2++;
}
// 왼쪽, 오른쪽 상관없이 결과 index는 +1이 된다.
index++;
}
// 왼쪽에 남은 부분을 저장한다. (오른쪽이 남았을 경우는 이미 배열 뒤쪽에 배치되어 있다.)
for(int i = 0; i <= mid-part1; i++) {
array[index + i] = temp[part1 + i];
}
}
public static void printArray(int[] array) {
for(int number : array) {
System.out.print(number + " ");
}
System.out.println();
}
}
마무리
이번에는 일정한 성능을 발휘하는 병합 정렬을 정리했습니다.
다음에는 Heap 자료 구조로 배열의 정리하여 정렬하는 힙 정렬을 정리하겠습니다.
감사합니다.
