안녕하세요.
이번에는 저번 포스팅에 이어
https://chanho0912.tistory.com/21
[C++/Algorithm] 정렬 알고리즘 이해하고 구현하기 (bubble, insertion, selection) #1
안녕하세요. 이번 포스팅에서는 기본적인 정렬 알고리즘인 버블 정렬 선택 정렬 삽입 정렬 이 세 가지에 대해 이해하고 구현해보는 포스팅을 진행해볼 예정입니다. 우선 정렬 알고리즘이 무엇
chanho0912.tistory.com
Merge Sort와 Quick Sort에 대해 알아보는 시간을 가져보겠습니다.
기본적으로 위 포스팅에서 진행한 선택, 삽입, 버블 정렬은 WorstCase(최악의 경우) O(n^2)의 성능을 가집니다. 즉 우리가 처리해야 할 데이터의 개수가 n 개라고 가정하면, n제곱에 비례하는 성능을 보입니다.
하지만 이번 포스팅에서 알아볼 병합정렬과, 퀵 정렬의 경우 보통 nlogn에 비례하는 성능을 보입니다.
nlogn 과 n제곱은 엄청난 차이를 가집니다. 가령 n이 1000만 되어도 nlogn = 1000 * 3이고, n제곱은 1000 * 1000입니다. n이 커질수록 이 둘의 차이는 더 커집니다.
즉 위 세 정렬보다 일반적으로 훨씬 좋은 성능을 갖는 알고리즘입니다.
그러면 병합 정렬부터 알아볼게요.
1. Merge Sort
Merge Sort는 기본적으로 Divide and Conquer전략을 따릅니다. 즉 일단 큰 문제를 작은 문제로 분할하고 정복하는 개념입니다. 따라서 MergeSort(병합 정렬)에서는 알고리즘을 두 단계로 진행합니다.
1) 분할
2) 병합
1) 분할
가령 다음과 같은 배열이 있다고 해봅시다.
우리는 위 배열을 다음과 같이 분할합니다.
즉 원소가 1개만 남을 때까지 계속 분할하는 것입니다.
이를 간단히 코드로 나타내면 다음과 같습니다.
void merge_sort(vector<int> &arr, int left, int right) {
if(left == right) return;
// 크기가 1일 경우 Return
int mid = (left + right) / 2;
// 중간점 찾기
merge_sort(arr, left, mid);
// 왼쪽 ~ 중간점
merge_sort(arr, mid+1, right);
// 중간점 + 1 ~ 오른쪽
}
left = 왼쪽 끝, right = 오른쪽 끝이라고 생각했을 때
왼쪽 = 오른쪽이면 크기가 1이므로 반환,
아니면 중간점 찾아서 왼쪽 ~ 중간점, 중간점+1 ~ 오른쪽 이렇게 다시 분할하여 재귀 함수를 실행합니다.
이렇게 되면 1개만 반환될 때까지 계속 인덱스가 분할됩니다.
모두 분할되었으면 이제 병합 단계로 넘어갑니다.
2) 병합
이제 쪼개진 원소를 저희가 원하는 순서대로 조립만 해주면 됩니다.
가령
이러한 식으로 오름차순으로 조립을 해 나가면 결국 최종적인 결과를 얻게 되는 구조입니다.
전체를 도식화하면 다음과 같습니다.
병합은 분할보다 코드가 직관적으로 머릿속으로 그려지지 않습니다. 차근차근해봅시다.
arr1 : {2, 5}의 원소를 갖는 블록과 arr2 : {3, 4}를 갖는 블록을 합치려면 어떻게 하면 될까요?
{2, 5}의 원소를 차례로 순회하는 변수 i와 {3, 4}의 원소를 차례로 순회하는 변수 j를 각각 선언한 뒤,
arr1[i] (2)와 arr2[j] (3)를 비교한 뒤, arr[i]가 작으면 arr[i] 를 결과 배열에 넣어줍니다. 그리고 i를 1 증가시켜줍니다.
그다음 arr1[i] (5)와 arr2[j] (3)을 비교하면 arr2[j]가 작기 때문에 arr[j]를 결과 배열에 넣어줍니다. 그리고 j를 1 증가시켜줍니다.
그다음 arr1[i] (5)와 arr2[j] (4)를 비교하면 arr2[j]가 작기 때문에 arr[j]를 결과 배열에 넣어줍니다.
마지막으로 arr1[i] 를 넣어주면
{2, 3, 4, 5}라는 결과 배열을 만들 수 있습니다.
한번 코드로 이해해 볼게요!
void merge(vector<int> &arr, int left, int right) {
int i = left, idx = left, mid = (left+right)/2;
int j = mid + 1;
while(i <= mid && j <= right) {
if(arr[i] <= arr[j]) {
tmp[idx++] = arr[i++];
}
else {
tmp[idx++] = arr[j++];
}
}
// 왼쪽 배열과 오른쪽 배열을 비교하여 작은것부터 차례로 넣어줌
if(i > mid) {
// i가 mid보다 크다는 것은 오른쪽 배열에 남아있는 원소가 있을 수 있음
for(int a = j; a <= right; a++){
tmp[idx++] = arr[a];
}
}
else {
// 반대경우 왼쪽 배열에 남아있는 원소가 있을 수 있음
for (int a = i; a <= mid; a++) {
tmp[idx++] = arr[a];
}
}
for (int a = left; a <= right; a++){
arr[a] = tmp[a];
// temp 배열을 원래 배열에 복사해줌
}
}
처음 while문을 보시면, i와 j라는 순회 인덱스를 선언해주고, 각 왼쪽 오른쪽 배열을 순회하며 더 작은 원소를 tmp라는 배열에 임시로 넣어줍니다.
그다음 if-else문을 보시면 마지막으로 넣은 원소가 왼쪽 배열에서 추가된 원소라면 오른쪽 배열에 남아있는 원소가 있을 수 있으니까 오른쪽 배열에 남은 원소를 모두 tmp배열에 넣습니다.
이때 병합에서는 left 배열과 right배열이 이전 단계에서 이미 정렬이 완료된 상태로 인수로 받기 때문에 추가적인 정렬은 하지 않고 순서대로 넣어주시면 됩니다.
마지막으로 임시 배열의 값을 원래 배열에 복사해주시면 병합이 완료됩니다!
자 그러면 전체 코드를 적으며 병합 정렬을 마무리하겠습니다.
#include <bits/stdc++.h>
using namespace std;
int tmp[10];
void merge(vector<int> &arr, int left, int right) {
int i = left, idx = left, mid = (left+right)/2;
int j = mid + 1;
while(i <= mid && j <= right) {
if(arr[i] <= arr[j]) {
tmp[idx++] = arr[i++];
}
else {
tmp[idx++] = arr[j++];
}
}
// 왼쪽 배열과 오른쪽 배열을 비교하여 작은것부터 차례로 넣어줌
if(i > mid) {
// i가 mid보다 크다는 것은 오른쪽 배열에 남아있는 원소가 있을 수 있음
for(int a = j; a <= right; a++){
tmp[idx++] = arr[a];
}
}
else {
// 반대경우 왼쪽 배열에 남아있는 원소가 있을 수 있음
for (int a = i; a <= mid; a++) {
tmp[idx++] = arr[a];
}
}
for (int a = left; a <= right; a++){
arr[a] = tmp[a];
// temp 배열을 원래 배열에 복사해줌
}
}
void merge_sort(vector<int> &arr, int left, int right) {
if(left == right) return;
// 크기가 1일 경우 Return
int mid = (left + right) / 2;
// 중간점 찾기
merge_sort(arr, left, mid);
// 왼쪽 ~ 중간점
merge_sort(arr, mid+1, right);
// 중간점 + 1 ~ 오른쪽
merge(arr, left, right);
}
int main(void){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
vector<int> arr = {5, 2, 3, 4, 7, 6, 1};
merge_sort(arr, 0, arr.size() - 1);
for (auto a : arr) {
cout << a << " ";
}
return 0;
}
2. Quick Sort
퀵 정렬은 이름에서 볼 수 있듯 굉장한 성능을 보여주는 정렬 알고리즘입니다.
퀵 정렬도 기본적으로 Divide and Conquer 전략을 사용합니다.
다만 MergeSort와 다른 점은 MergeSort는 모든 배열을 하나가 될 때까지 쪼개어 병합하지만, QuickSort는 기본적으로 pivot이라는 어떠한 비교 기준이 되는 값을 정하여 pivot보다 작으면 왼쪽으로, 크면 오른쪽으로 분할합니다.
만약에 5가 pivot이면,
그림과 같이 5를 기준으로 보다 작은 원소는 왼쪽으로, 큰 원소는 오른쪽으로 배치하게 됩니다.
여기서는 부분 정렬을 진행하지 않고 그냥 옮기기만 합니다.
그러면 다시 {2, 3, 4, 1}과 {7, 6}을 다시 pivot값 기준으로 분할 다시 분할... 을 하다 보면
결국 {1, 2, 3, 4, 5, 6, 7}의 정렬된 배열을 얻을 수 있게 됩니다.
void quick_sort(vector<int> &arr, int left, int right) {
if(left >= right) return;
int pivot = partition(arr, left, right);
// pivot 값 선정 및 분할
quick_sort(arr, left, pivot - 1);
quick_sort(arr, pivot + 1, right);
}
따라서 전반적인 코드 로직은 다음과 같이 작동합니다.
분할을 한 뒤, 다시 pivot값 기준으로 왼쪽에 대해 퀵 정렬 오른쪽에 대해 퀵 정렬을 실행합니다.
만약에 pivot값으로 왼쪽 끝 원소를 사용했다고 가정해 보겠습니다.
그러면 partition 함수는 다음과 같이 진행됩니다.
int partition(vector<int> &arr, int left, int right) {
int pivot = arr[left];
// 왼쪽 끝 값을 pivot으로 지정
int i = left, j = right;
while(i < j) {
// left < right인 동안 while 루프 수행
while(arr[j] > pivot) {
j--;
// 오른쪽 끝부터 진행하여 첫 번째로 pivot보다 작은 값을 만날 때까지 j--
}
while(arr[i] <= pivot && i < j) {
i++;
// 왼쪽부터 진행하여 첫 번째로 pivot보다 큰 값을 만날 때까지 i++
}
swap(arr[i], arr[j]);
// 왼쪽에서 pivot보다 작은값과 오른쪽에서 pivot보다 큰 값을 swap
}
arr[left] = arr[i];
arr[i] = pivot;
// 끝난 지점에 pivot값 삽입
return pivot;
// pivot 반환
}
그러면 전체 코드는 다음과 같이 진행됩니다.
int partition(vector<int> &arr, int left, int right) {
int pivot = arr[left];
// 왼쪽 끝 값을 pivot으로 지정
int i = left, j = right;
while(i < j) {
// left < right인 동안 while 루프 수행
while(arr[j] > pivot) {
j--;
// 오른쪽 끝부터 진행하여 첫 번째로 pivot보다 작은 값을 만날 때까지 j--
}
while(arr[i] <= pivot && i < j) {
i++;
// 왼쪽부터 진행하여 첫 번째로 pivot보다 큰 값을 만날 때까지 i++
}
swap(arr[i], arr[j]);
// 왼쪽에서 pivot보다 작은값과 오른쪽에서 pivot보다 큰 값을 swap
}
arr[left] = arr[i];
arr[i] = pivot;
// 끝난 지점에 pivot값 삽입
return pivot;
// pivot 반환
}
void quick_sort(vector<int> &arr, int left, int right) {
if(left >= right) return;
int pivot = partition(arr, left, right);
// pivot 값 선정 및 분할
quick_sort(arr, left, pivot - 1);
quick_sort(arr, pivot + 1, right);
}
int main(void){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
vector<int> arr = {5, 2, 3, 4, 7, 6, 1};
quick_sort(arr, 0, arr.size() - 1);
for (auto a : arr) {
cout << a << " ";
}
return 0;
}
3. MergeSort와 QuickSort의 성능
우선 병합 정렬의 경우 분할과 정복 모두 2의 제곱 연산, 즉 반씩 나누고 두배로 합치며 진행합니다.
이 그림에서 보듯 전체 원소에 대해 (n개),
도식도에서 보듯 높이가 logn 즉 분할, 정복 과정에서 logn에 비례하는 시간 복잡도를 가지기 때문에, nlogn에 비례하는 시간 복잡도를 항상 갖습니다.
하지만 QuickSort의 경우 항상 nlogn에 비례하는 성능을 가진다고 보장할 수 없습니다.
저희가 위에서 설계한 코드를 사용할 때 만약에
{7, 6, 5, 4, 3, 2, 1}의 역순으로 정렬된 배열이 들어온다면 어떻게 될까요?
7이 피봇이면 모든 원소를 옮기고, {1, 6}에 대해 다시 quicksort진행,
그다음 6이 피봇이면...
즉 n^2에 비례하는 성능을 보입니다.
하지만 실제로 여러 framework의 내장 함수나 실제로 적용되는 곳에서는 merge sort보다 quick sort를 사용합니다.
그 이유는 무엇일까요?
1. worst case는 실제 적용 사례에서 거의 없습니다.
실제로 pivot을 선정하는 알고리즘에도 여러 종류가 있고, 항상 worst 하게 pivot을 선정하기가 더 어렵습니다.
따라서 worst case를 고려하여 quick sort를 사용하지 않기에는 평균적인 case들의 성능을 비교했을 때 quick sort가 너무 우수합니다.
2. merge sort는 기본적으로 메모리를 많이 사용합니다.
기본적으로 merge sort는 병합 과정에서 매번 임시 배열을 생성 복사 해제 과정을 반복해야 한다. 위 사례에서는 간단한 예시이기 때문에 10이라는 작은 size를 전역 변수로 사용하였지만, 실제 데이터는 몇만, 몇십만 혹은 그 이상이 대부분이다. 이러한 경우에 매번 위와 같은 작업을 하는 것은
메모리 사용량을 너무 높이고,
그로 인해 오버헤드가 증가하여 성능이 떨어집니다.
즉 단순 연산 횟수만 비교할 것이 아니라, 메모리에 적재하고, 복사하고 해제하는 여러 부수적인 요인들 때문에 실성능은 QuickSort가 앞서게 됩니다.
여기까지 총 5개의 정렬 알고리즘에 대해 알아보았습니다. 추가로 다른 정렬 알고리즘에 대해 추후 포스팅할 예정입니다.
*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.
'Algorithm > Algorithm Logic' 카테고리의 다른 글
| [Algorithm] DFS, BFS 정리 (0) | 2021.07.12 |
|---|---|
| [C++/Algorithm] 투 포인터, 구간 합 이해하기 (0) | 2021.07.05 |
| [C++/Algorithm] 정렬 알고리즘 이해하고 구현하기 (bubble, insertion, selection) #1 (0) | 2021.06.27 |
| [C++/Algorithm] 순열과 조합 구현하기 (0) | 2021.06.23 |
| [C++/Algorithm] upper_bound, lower_bound 이해하기 (2) | 2021.06.22 |
