개념 요약
- 분할 정복을 통해 구현한다.
- 빠른 정렬로 분류되며 퀵 정렬같이 많이 언급된다.
- 정렬되지 않은 배열을 각각 하나의 원소만 포함하는 n개로 분할한다.(결국 원소 하나씩 분할)
- 분할했던 역순으로 정렬하면서 병합한다.
정렬 과정
- 배열의 길이가 1이라면 정렬된 것으로 본다.
- 가져온 배열을 이등분하여 분할한다.
- 분할한 배열을 재귀적으로 다시 분할한다.
- 위 과정에서 이등분한 배열을 다시 하나의 정렬된 배열로 합병한다.(임시 배열)
- 임시 배열의 결과를 원래 배열에 복사한다.
코드
void merge(std::vector<int> &unsorted_array, int left, int mid, int right)
{
// 임시로 사용할 vector 정의
std::vector<int> left_array, right_array;
for (int idx = left; idx < right + 1; ++idx)
{
if (idx < mid + 1)
left_array.push_back(unsorted_array[idx]);
else
right_array.push_back(unsorted_array[idx]);
}
int i = 0, j = 0, k = left;
while (i < left_array.size() && j < right_array.size())
{
// 대소비교를 통해 원래 vector에 삽입
if (left_array[i] < right_array[j])
unsorted_array[k++] = left_array[i++];
else
unsorted_array[k++] = right_array[j++];
}
// 남은것들 삽입
while (i < left_array.size())
unsorted_array[k++] = left_array[i++];
while (j < right_array.size())
unsorted_array[k++] = right_array[j++];
}
void merge_sort(std::vector<int> &unsorted_array, int left, int right)
{
if (left < right)
{
// 증긴깂 결정
int mid = (right + left) / 2;
// 분할
merge_sort(unsorted_array, left, mid);
merge_sort(unsorted_array, mid + 1, right);
// 정복, 결합
merge(unsorted_array, left, mid, right);
}
}
시간 복잡도
- 평균, 최선, 최악 모두 $O(nlogn)$를 갖는다.
공간 복잡도
- $O(n)$
장단점
- 효율적이며 안정적인 정렬 방식이다.
- 연결 리스트로 저장 시 유리하다.
- 정복, 결합과정에서 임시 배열이 필요하다.
'CS공부 > Algorithm' 카테고리의 다른 글
기수 정렬(Radix Sort) (0) | 2022.06.22 |
---|---|
힙 정렬(Heap Sort) (0) | 2022.06.21 |
퀵 정렬(Quick Sort) (0) | 2022.06.20 |
삽입 정렬(Insertion Sort) (0) | 2022.06.20 |
선택 정렬(Selection Sort) (0) | 2022.06.20 |