[C++] Merge Sort, Quick Sort

정의

병합 정렬과 퀵 정렬은 분할 정복 알고리즘이며, 정렬 속도가 매우 빠르다.

• 퀵 정렬이 평균적으로 더 빠르지만 오름차순(또는 내림차순)일 때 최악의 경우에 O(n²)이다
• 하지만 Algorithm 헤더파일의 sort 함수는 퀵 정렬이며, 아래의 방식으로 최악의 경우를 피한다 
  
  • 피벗을 랜덤으로 지정
  • 3개의 피벗 중에 중앙값을 사용

	Merge Sort	Quick Sort
공통점	평균 O(NlgN)
장점	stable_sort가 가능	임시 배열을 사용하지 않아서 cache hit rate가 높음

 

Merge Sort 예시코드

#include <bits/stdc++.h>
using namespace std;

int arr[1000001];
int tmp[1000001];

void merge(int st, int en){
    int mid = (st+en)/2;
    int lo = st; // arr[st:mid]
    int hi = mid; // arr[mid:en]

    for(int i = st; i < en; i++){
        if(hi == en) tmp[i] = arr[lo++];
    else 
        if(lo == mid) tmp[i] = arr[hi++];
    else 
        if(arr[lo] <= arr[hi]) tmp[i] = arr[lo++];
    else 
        tmp[i] = arr[hi++];
    }
    for(int i = st; i < en; i++) // 임시저장 값을 재할당
        arr[i] = tmp[i]; 
}

void merge_sort(int st, int en){
    if(en-st == 1) 
        return;
    int mid = (st+en)/2;
    merge_sort(st,mid);
    merge_sort(mid,en);
    merge(st,en);
}

int main(void){
   int n;
   cin >> n;
   for(int i = 0; i < n; i++) 
       cin >> arr[i];

   merge_sort(0, n);

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

 

Quick Sort 예시코드

#include <bits/stdc++.h>
using namespace std;

int arr[1000001];

void quick_sort(int st, int en) {
    if(en <= st+1) 
        return;

    int pivot = arr[st];
    int l = st+1;
    int r = en-1;

    while(true){
        while(l <= r && arr[l] <= pivot) 
            l++;
        while(l <= r && arr[r] >= pivot) 
            r--;
        if(l > r) 
            break;
        swap(arr[l], arr[r]);
    }
    swap(arr[st], arr[r]);
    quick_sort(st, r);
    quick_sort(r+1, en);
}

int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) 
        cin >> arr[i];

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