<문제 소개>
<소스 코드>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <cmath>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstdlib>
using namespace std;
void Merge(vector<int>& v, int left, int mid, int right)
{
int i = left; // 왼쪽 부분 시작지점
int j = mid + 1; // 오른쪽 부분 시작지점
int k = left; // 원소를 넣을 위치
vector<int> sortedVec(v.size()); // 정렬된 벡터를 저장할 공간
// 왼쪽부분과 오른쪽 부분의 원소들을 하나씩 차례로 비교하여 더 작은 원소를 sortedVec에 넣음.
// 왼쪽 부분과 오른쪽 부분은 이미 오름차순으로 정렬되어있는 상태이므로 차례로 비교하면 됨.
while (i <= mid && j <= right)
{
if (v[i] <= v[j])
{
// 왼쪽 부분의 원소가 더 작은 경우
// -> 왼쪽 부분의 원소 저장 후 왼쪽 부분만 다음 원소로 넘어감
sortedVec[k] = v[i];
i++;
}
else
{
// 오른쪽 부분의 원소가 더 작은 경우
// -> 오른쪽 부분의 원소 저장 후 오른쪽 부분만 다음 원소로 넘어감
sortedVec[k] = v[j];
j++;
}
k++;
}
// 위의 과정이 끝나면 i = mid + 1 이 되거나 j = right + 1 이 된다.
if (i > mid)
{
// i = mid + 1인 경우 -> 왼쪽 부분의 마지막 원소(최대값)이 오른쪽 부분의 원소들 중 하나보다 작은 경우
// -> 오른쪽 부분의 나머지 값들(왼쪽 부분의 최대값보다 큰 값들) 저장
for (int p = j; p <= right; p++)
{
sortedVec[k] = v[p];
k++;
}
}
else
{
// j = right + 1인 경우 -> 오른쪽 부분의 마지막 원소(최대값)이 왼쪽 부분의 원소들 중 하나보다 작은 경우
// -> 왼쪽 부분의 나머지 값들(오른쪽 부분의 최대값보다 큰 값들) 저장
for (int p = i; p <= mid; p++)
{
sortedVec[k] = v[p];
k++;
}
}
// 정렬해서 저장한 벡터 sortedVec의 값들을 다시 원래 벡터로 넣어줌
for (int p = left; p <= right; p++)
{
v[p] = sortedVec[p];
}
}
void MergeSort(vector<int>& v, int leftIndex, int rightIndex)
{
if (leftIndex < rightIndex)
{
int mid = (leftIndex + rightIndex) / 2;
MergeSort(v, leftIndex, mid); // 왼쪽 부분을 분할
MergeSort(v, mid + 1, rightIndex); // 오른쪽 부분을 분할
Merge(v, leftIndex, mid, rightIndex); // 분할된 왼쪽과 오른쪽 부분을 정렬 후 병합
}
}
int main()
{
int N;
cin >> N;
vector<int> v;
// 원소 입력
while (N > 0)
{
int x;
cin >> x;
v.push_back(x);
N--;
}
// 6. 병합 정렬
// - 분할 정복의 대표적인 예시
// 1. Divide(분할) : n개의 원소를 갖는 배열을 n/2개의 원소를 갖는 작은 배열 2개로 나눈다.
// 2. Conquer(정복) : 각각의 작은 배열들을 정렬한다.
// 3. Combine(병합) : 정렬된 작은 배열들을 병합한다.
MergeSort(v, 0, v.size() - 1);
// 원소 출력
for (int i = 0; i < v.size(); i++)
{
cout << v[i] << endl;
}
return 0;
}<풀이과정>
1. MergeSort()
1-1. 인자로 벡터 v와 나눌 부분의 맨 왼쪽 인덱스 leftIndex, 맨 오른쪽 인덱스 rightIndex를 받는다.
1-2. leftIndex가 rightIndex보다 작으면 중간 인덱스 mid를 선언하고, 해당 값을 이용해 왼쪽 부분인 leftIndex부터 mid까지, 오른쪽 부분인 mid+1부터 rightIndex까지에 대해 MergeSort()를 진행하여 가장 작은 단위로 쪼갠다.
2. Merge()
2-1. MergeSort()로 인해 가장 작은 단위로 쪼개진 부분들을 맨 왼쪽부터 차례로 정렬한 뒤 병합한다.
2-2. 인자로는 벡터 v와 분할된 벡터의 가장 왼쪽 인덱스 left, 중간 인덱스 mid, 오른쪽 인덱스 right를 받는다.
2-3. i = left로 왼쪽 부분의 시작지점을 나타내고, j = mid + 1로 오른쪽 부분의 시작지점을 나타낸다. 그리고 k는 임시 벡터의 원소를 넣을 위치로 처음에는 왼쪽부분의 시작지점에 넣어야 하므로 k = left로 초기화 시킨다.
2-4. 정렬된 벡터를 저장할 임시벡터 sortedVec를 v의 크기를 가진 벡터로 초기화하여 선언한다.
2-5. 이제 while문을 이용해 왼쪽부분과 오른쪽부분의 원소를 각각 비교하여 작은 수를 임시벡터 sortedVec에 넣는 과정을 반복한다.
2-6. 만약 왼쪽부분에 넣었다면 sortedVec[k] = v[i]를 해주고, i를 증가시켜 왼쪽부분이 다음 원소를 가리키게 한다.
2-7. 마찬가지로 오른쪽부분에 넣었다면 sortedVec[k] = v[j]를 해주고, j를 증가시켜 오른쪽부분이 다음 원소를 가리키게 한다.
2-8. 매 반복마다 k는 증가시켜 sortedVec에 차례대로 담는다.
2-9. 왼쪽과 오른쪽 부분 중 어느 한쪽의 원소를 다 소진한 경우에는 반복을 끝내야 하고, 이 조건은 i > mid 이거나, j > right인 경우이다. 그러므로 while문은 i <= mid 이면서 j <= right를 동시에 만족하는 경우에만 반복해야한다.
2-10. 이처럼 while문이 끝난 경우 i = mid+1이거나 j = right+1인 경우 두가지로 나눌 수 있는데 i가 mid+1인 경우는 왼쪽부분을 모두 소진한 것이므로, 오른쪽부분에 사용하지 않은 나머지 원소들을 그대로 저장해준다.
2-11. 반대의 경우도 마찬가지로 왼쪽부분의 사용하지 않은 나머지 원소들을 그대로 저장해준다.
2-12. 위의 과정이 모두 끝나면 sortedVec는 왼쪽부분과 오른쪽부분이 정렬되어 합쳐진 벡터가 되고, 이렇게 정렬된 부분을 원래 벡터 v에 넣어주어 원래 벡터를 정렬시킨다.
3. 위의 과정이 모두 끝나게 되면 모든 부분이 분할되고 정렬되어 병합되는 과정을 거쳐 오름차순으로 정렬이 완료된다.
<코멘트>
이번엔 여섯번째 방법인 병합 정렬로 풀어보았다!
코드 해석하는데 힘이 들었다..ㅋㅋ 아직 많이 부족함을 느낀다..ㅠㅠ
- 병합 정렬 -
장점
- 퀵 정렬과 비슷하게 분할하는 과정에서 logn 만큼에 시간이 걸리고, 최종적으로 보면 nlogn 만큼의 시간이 걸린다.
- 하지만 퀵 정렬과 달리, pivot을 설정하거나 그런 과정 없이 무조건 절반으로 분할하기에 pivot에 따라 성능이 달라지는 경우가 없다. 그러므로 항상 O(nlogn) 이라는 시간복잡도를 갖게된다.
단점
- 병합 정렬은 임시배열에 원본배열을 계속해서 옮겨주면서 정렬하므로 추가적인 메모리가 필요하다.
- 추가적인 메모리를 할당할 수 없을 경우, 데이터가 최악으로 있다면, 퀵보다는 병합 정렬이 훨씬 빠르기 때문에 병합 정렬을 사용하는 것이 맞지만, 추가적인 메모리를 할당할 수 없다면 병합 정렬은 사용할 수 없기 때문에 퀵 정렬을 사용해야 한다.
특징
1. 시간복잡도
- 최악 : O(nlogn)
- 평균 : O(nlogn)
2. 공간복잡도 O(n)
3. not in-place정렬 - 분할한 작은 배열을 위한 저장공간이 따로 필요하기 때문
4. stable정렬 - 중복된 키 값의 순서가 정렬 후에도 유지되기 때문
<cf>
1. stable vs not-stable
- stable 정렬은 중복된 키 값이 있을 때 이를 순서대로 정렬하는 알고리즘을 뜻함.
- 즉 , 정렬했을 때 중복된 키 값이 원래 순서대로 정렬되어있으면 stable 아니면 not-stable이다.
2. in-place vs not in-place
- in- place 정렬은 원소들의 개수에 비해 충분히 무시할 만한 저장 공간만을 더 사용하는 정렬 알고리즘을 뜻함.
- not in-place 정렬은 원소들의 개수에 비례하여 저장 공간을 더 사용하는 정렬 알고리즘을 뜻함.
<제출 결과>
<병합 정렬> - 준수한 시간대
<삽입 정렬> - 버블/선택 정렬보다 빠른 시간대, 밑의 결과는 매번 swap했을 경우
<힙 정렬> - 퀵 정렬보다 느린 시간대
<퀵 정렬> - 준수한 시간대
<비교 - 선택정렬> - 버블정렬에 비해 조금 더 빠르다는 것을 알 수 있음
<비교 - 버블정렬>
