정렬 알고리즘은 종류가 엄청나게 많다.
하지만 우리는 다 알아보지는 않을 것이고 기본적인 정렬에 대해서만 알아볼 것이다.
정렬
솔직히 그냥 algorithm에 sort를
vector<int> v{1, 5, 3, 4, 2};
std::sort(v.begin(), v.end());이런식으로 사용하면 되지만
정렬은 면접에 정말 많이 나오기 때문에 공부를 해야한다.
Bubble Sort
일단 먼저 Bubble Sort에 대해서 알아볼 것이다.
버블 소트는 어떻게 동작하는 것이냐?
만약 15342가 있다면
1과 5를 비교 해줌 5가 더 크기에 바꾸지 않기
5와 3을 비교 해줌 3이 더 작기에 둘이 자리를 바꿈
13542
5와 4를 비교 해줌 4가 더 작기에 둘이 자리를 바꿈
13452
5와 2를 비교 해줌 2가 더 작기에 둘이 자리를 바꿈
13425
이런식으로 큰 수를 뒤로 밀어주고 한 턴이 지나게 되면 가장 큰 수가 제일 뒤로 가게 될 것이고,
맨 뒤에 숫자를 빼고 비교를 해주면 된다.
이런식으로 거품처럼 정렬이 되기때문에 Bubble Sort라고 부른다.
그럼 구현을 해보자
void BubbleSort(vector<int>& v)
{
const int n = v.size(); // 데이터 개수
for(int i = 0; i < n -1; i++)
{
for(int j = 0; j < n - 1 - i; j++)
{
if(v[j] > v[j + 1])
{
//int temp = v[j];
//v[j] = v[j + 1];
//v[j + 1] = temp;
swap(v[j], v[j + 1]);
}
}
}
}구현은 이런식으로 할 수 있다.
그러면 시간복잡도는 어떤식으로 구할 수 있을까?
for문이 2개 있기때문에 O(N^2)이다.
정말 비효율적인 것이다.
Selection Sort
비효율적인 정렬 하나를 더 알아볼 것인데 그게바로 선택 정렬이다.
선택 정렬은 아래처럼 동작한다.
15342가 있을 때
쭉 스캔을 한 뒤에
가장 작은애를 찾기
1
두번째로 작은애
2
이런식으로 순차적으로 골라서 하는 것이다.
구현을 해본다면
void Selection Sort(vector<int>& v)
{
const int n = v.size();
for(int i = 0; i < n - 1; i++)
{
int bestIdx = i;
for(int j = i + 1; j < n; j++)
{
if(v[j] < v[bestId x])
bestIdx = j;
}
if(i != bestIdx)
swap(v[i], v[bestIdx]);
}
}이런식으로 선택정렬을 할 수 있다.
이것도 시간복잡도를 생각해본다면
O(N^2)일 것이다.
HeapSort
이제 좀 효율적인것으로 넘어가게 될 것이다.
자료구조에서 heap은 우선순위큐를 만들때 사용한 heap tree이다.
개념적으로 보면 우선순위큐를 사용하여 구현을 할 수 있다.
void HeapSort(vector<int>& v)
{
priority_queue<int, vector<int>, greater<int>> pq;
for(int num : v)
pq.push(num);
v.clear();
while(pq.empty() == false)
{
v.push_back(pq.top());
pq.pop();
}
}이런식으로 구현을 해줄 수 있다.
그럼 시간복잡도를 구해보자
pq에 데이터를 추가할 때 시간복잡도가 O(logN)이다.
for문안에 들어가 있기에 logN을 N번 하는 것이기에
전체 추가를 해주는 부분은 O(NlogN)이 될 것이다.
그리고 pq.top()꺼내는 것은 O(1)이지만 pop()을 하면서 트리를 다시 정렬시키기 때문에 top()은 무시하고 O(logN)이 될 것이다.
그리고 while문안에 들어가있고 while문은 pq가 빌 때까지인데 처음에 N개를 넣었으므로 O(NlogN)이 될 것이다.
최종적으로
2NlogN이지만 상수는 중요하지 않기때문에
시간복잡도는 O(NlogN)이다.
이렇게 하면 전보다 빠르 NlogN이 나왔다.
이제 앞으로 좋은 정렬은 거의 NlogN이라고 보면 된다.
그럼 이제 난이도를 높여서 병합 정렬과 퀵 정렬를 알아볼 것이다.
병합 정렬같은 경우는 병합 정렬자체가 중요한 것이 아닌 거기에 사용되는 테크닉이 중요하다. (다른 알고리즘구현할 때도 분할 정복이라는 테크닉이 사용되기 때문이다.
병합 정렬
병합 정렬에는 분할 정복(Divide and Conquer)이라는 방식을 이용한다.
분할(Divide) 문제를 단순하게 분할
정복(Conquer) 분할된 문제를 해결
결합(Combine) 결과를 취합하여 마무리
예들 들어 카드가 8장이 있다고 생각해보자
[3][K][7][2][J][4][8][9] << 8개 1 (1세트)
이걸 두개로 나눠서 정렬을 한다고 해보자
[3][K][7][2] [J][4][8][9] << 4개 2 (2세트)
그리고 계속 분할을 해보자
[3][K] [7][2] [J][4] [8][9] << 2개 4 (4세트)
[3][K] [7][2] [J][4] [8][9] << 1개 8 (8세트)
이거를 하나씩 조립을 해보자 (순서에 맞게)
[3]이랑 [K]가 붙으면 [3][K]가 맞기에 그대로 나두고
[7]이랑 [2]가 붙으면 [2][7]이 맞기에 순서를 바꿔준다.
그러면 뒤에 것도 [4][j] [8][9]가 될 것이다.
[3][K] [2][7] [4][J] [8][9] << 2개 4 (4세트)로 다시 바뀌게 된다.
여기부터는 정렬된 애들끼리 병합하는 것은 쉽게 될 것이다.
[2][3][7][K] [4][8][9][J] << 4개 2 (2세트)
둘이 비교해서 꺼내서 병합시켜 줄 수 있다.
그래서 이러한 분할 정복은 다른 알고리즘에서도 응용이 되기 때문에 중요하다.
그럼 구현은 어떤식으로 할 수 있을까?
void MergeResult(vector<int>& v, int left, int mid, right)
{
int leftIdx = left;
int rightIdx = mid + 1;
vector<int> temp;
while(leftIdx <= mid && rightIdx <= right)
{
if(v[leftIdx] <= v[rightIdx])
{
temp.push_back(v[leftIdx]);
leftIdx++;
}
else
{
temp.push_back(v[rightIdx]);
rightIdx++;
}
}
if(leftIdx > mid)
{
while(rightIdx <= right)
{
temp.push_back(v[rightIdx]);
rightIdx++;
}
}
else
{
while(rightIdx <= right)
{
temp.push_back(v[leftIdx]);
leftIdx++;
}
}
for(int i = 0; i < temp.size(); i++)
v[left + i] = temp[i];
}
void MergeSort(vector<int>& v, int left, int right)
{
if(left >= right) // 1개 남았을 때
return;
int mid = (left + right) / 2;
MergeSort(v, left, mid);
MergeSort(v, mid + 1, right);
MergeResult(v, left, mid ,right);
}이렇게 구현을 해볼 수 있다.
하지만 처음보면 이해를 못할 수도 있기에 디버깅을 돌려보면서 이해하는 방법도 좋다.
시간복잡도를 보자면 나누는 부분(MergeSort)은 O(logN)이고 정렬과 동시 병합하는 부분(MergeResult)은 O(N)이다.
그래서 합쳐서 보면 병합 정렬은 O(NlogN)이라고 볼 수 있다.
효율적인 방식에 속함
여기서 의미있는 점은 분할을 하고 다른 부분을 다른 곳에 주더라도 서로 의존적인것이 아니기 때문에 분할 한 것은 병렬로 처리하게 된다면 유용하게 될 수도 있다.
마무리
다음에는 끝판왕이 퀵정렬을 알아볼 것이다.
병합정렬과 난이도가 비슷하고 개념도 비슷하다고 볼 수 있다.
