[알고리즘 구현] Quick Sort

Quick sort

• divide and conquer 전략을 사용한다. 즉 재귀를 사용
• 평균 O(NlongN), 최악의 경우 O(N^2)이 나올 수 있다.
• 이는 pivot을 무엇으로 선택하느냐에 따라 성능이 차이가 날 수 있다.(대부분 중간값 사용)
• quick sort는 빠른데다가 merge sort와 다르게 메모리를 추가로 사용하지 않는다.
• 참고로 merge sort는 O(N), quick sort는 O(1)의 공간복잡도를 나타낸다.

구현 (C++)

void quickSort(int left, int right){
    if(left >= right) return;
    
    int pivot = arr[(left + right)/2];
    int _left = left;
    int _right = right;
    
    while(_right >= _left){
        while(arr[_left] < pivot) _left++;
        while(arr[_right] > pivot) _right--;
        if(_left <= _right){
            swap(arr[_left], arr[_right]);
            _left++;
            _right--;
        }
    }
    quickSort(left, _right);
    quickSort(_left, right);
}