[알고리즘] Merge sort와 Quick sort 비교 및 구현

Merge Sort

먼저 구현부터 해보자. 재귀 형태로 구현했다.

• 함수 정의
  void merge_sort(int start, int end) : start ~ end - 1까지 병합 정렬을 실행한다.
• base condition
  if(길이가 1) return;
• 재귀식
  배열을 반으로 쪼개서 병합정렬을 한 후 merge 함수를 써서 병합하면 된다. merge 함수는 정렬된 두 배열을 병합하는 함수이다.
  배열을 반으로 쪼개서 병합정렬을 한다는 건 귀납적 사고를 통해 재귀식을 구성했다고 생각하면 된다. 길이가 4인 배열을 병합정렬 할 수 있다고 가정하면 길이가 8인 배열은 길이가 4인 배열을 합치면 끝이다. 이런 느낌으로 구현해 보자.

#include <iostream>
#include <algorithm>
using namespace std;

int n = 10;
int input_arr[1000001] = {15, 25, 22, 357, 16, 23, -53, 12, 46, 3};
int temp_arr[1000001]; // merge 함수에서 리스트 2개를 합친 결과를 임시로 저장하고 있을 변수

// mid = (start+end)/2라고 할 때 input_arr[start:mid], input_arr[mid:end]은 이미 정렬이 되어있는 상태일 때 input_arr[start:mid]와 input_arr[mid:end]을 합친다.
void merge(int start, int end)
{
    int mid = (start + end) / 2;
    int left_idx = start;
    int right_idx = mid;
    for (int i = start; i < end; i++)
    {
        if (right_idx == end)
            temp_arr[i] = input_arr[left_idx++];
        else if (left_idx == mid)
            temp_arr[i] = input_arr[right_idx++];
        else if (input_arr[left_idx] <= input_arr[right_idx])
            temp_arr[i] = input_arr[left_idx++];
        else
            temp_arr[i] = input_arr[right_idx++];
    }
    for (int i = start; i < end; i++)
        input_arr[i] = temp_arr[i];
}

void merge_sort(int start, int end)
{
    if (start + 1 == end)
        return; // 길이 1인 경우
    int mid = (start + end) / 2;
    merge_sort(start, mid); // input_arr[start:mid]을 정렬한다.
    merge_sort(mid, end);   // input_arr[mid:end]을 정렬한다.
    merge(start, end);      // input_arr[start:mid]와 input_arr[mid:end]을 합친다.
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    merge_sort(0, n);
    for (int i = 0; i < n; i++)
        cout << input_arr[i] << ' '; // -53 3 12 15 16 22 23 25 46 357
}

 

코드에서 보면 배열을 합치는 과정에서 

else if (input_arr[left_idx] <= input_arr[right_idx])
    temp_arr[i] = input_arr[left_idx++];

이 부분이 꽤 중요하다. 부등호가 <=가 아닌 <로 들어간다면 결과가 똑같아 보이지만 Merge sort의 큰 장점인 Stable Sort를 잃게 된다. Stable Sort란 여러 가지의 우선순위가 있을 때 그것을 지키며 정렬하는 특성이다. 예를 들어 x, y 좌표를 정렬한다고 치면, y 좌표를 기준으로 Merge Sort를 하고 x 좌표를 기준으로 Merge Sort를 해버리면 x 좌표가 같은 경우 y 좌표를 기준으로 정렬한 상태가 된다. 이 특성이 꽤나 중요하다.

---

Quick Sort

퀵 정렬은 pivot이라는 기준점을 기준으로 좌우를 pivot에 맞게 정렬하면서 재귀적으로 전체 정렬하는 알고리즘이다. 구현을 해보자. merge sort와 비슷하게 재귀식만 잘 짜서 구현하면 된다.

left_p는 왼쪽부터 시작하는 포인터이다. 결과물은 left_p부터 오른쪽에 쭉 pivot보다 작은 수가 있어야 한다. right_p는 정반대로 동작한다.

따라서 left_p가 오른쪽으로 하나씩 이동하다가 pivot보다 큰 수를 만나면 멈춘다. right_p는 오른쪽에서 시작해서 pivot보다 작은 수를 만나면 멈춘다. 그리고 그 둘을 바꾸기를 계속 반복하면 최종 결과물은 0번에 pivot, right_p부터 그 왼쪽으로는 pivot보다 작은 수, 오른쪽으로는 pivot보다 큰 수가 있을 것이다. 마지막으로 right_p와 pivot을 바꾸면 pivot 왼쪽에는 pivot보다 작은 수, 오른쪽에는 큰 수로 이루어지고 pivot을 기준으로 쪼개서 재귀적으로 정렬을 돌리면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int n = 10;
int arr[1000001] = {15, 25, 22, 357, 16, 23, -53, 12, 46, 3};

void quick_sort(int start, int end)
{
    if (end <= start + 1)
        return;
    int pivot = arr[start];
    int left_p = start + 1; // 왼쪽부터 시작하는 포인터, 결과물은 얘 오른쪽에 있는건 pivot 보다 커야함
    int right_p = end - 1;
    while (1)
    {
        while (left_p <= right_p && arr[left_p] <= pivot)
            left_p++;
        while (left_p <= right_p && arr[right_p] >= pivot)
            right_p--;
        if (left_p > right_p)
            break;
        swap(arr[left_p], arr[right_p]);
    }
    swap(arr[start], arr[right_p]);
    quick_sort(start, right_p);
    quick_sort(right_p + 1, end);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    quick_sort(0, n);
    for (int i = 0; i < n; i++)
        cout << arr[i] << ' ';
}

 

Quick Sort는 병합 정렬보다 평균적으로 빠른 시간을 자랑한다. 같은 O(n log n)이지만 퀵 정렬이 평균적으로 더 빠르다. 하지만 pivot을 어떻게 정하느냐에 따라 O(n^2)까지 걸릴 수 있다. 따라서 정렬을 직접 구현해야 한다면 힙 정렬이나 병합 정렬로 반드시 구현하자. 우리가 많이 쓰는 stl의 정렬은 퀵 정렬이지만 pivot을 데이터에 따라 다르게 정하거나 배열의 깊이가 깊어지면 힙 소트로 정렬한다. 

 

퀵 정렬의 또 다른 특성은 추가적인 공간을 필요로 하지 않는다는 것이다. 병합 정렬과 비교해서 평균적으로 더 빠르고 Unstable하고 추가적인 공간을 필요로하지 않는다는 점만 기억해 두자.