Quick Sort (퀵 정렬)

참고자료: 유투버 동빈나 님의 실전 알고리즘 강좌 

정렬방법에는 시간복잡도  $O(N^2)$ 을 갖는 Selection Sort (선택 정렬), bubble sort(버블정렬), insertion sort(삽입정렬)등이 있다. 이 방법들은 프로그래밍이 직관적이고 쉽지만 데이터의 개수의 제곱으로 계산량이 증가하기 때문에 많은 데이터를 처리해야 하는 작업에는 적합하지 않다. 이번에는 시간복잡도 $O(N*logN)$을 갖는 Quick Sort에 대해서 알아보도록 하겠다.

Quick Sort는 대표적인 분할 정복식 알고리즘(Divide and Conquer Algorithm, DAC) 이라고 한다. DAC에 대해 간단히 알아보면,

1. Divide: 문제를 작은 sub-problem들로 나누는것
2. Conquer: 문제가 해결될 때 까지 재귀적으로 sub-problem을 해결하는 것
3. Combine: sub-problem의 결과를 합쳐서 최종 결과를 도출 하는 것

이다. 즉, quick sort는 특정한 기준값 (Pivot)을 정한 뒤 큰 값과 작은 값으로 나누고 큰값부분, 작은 값 부분을 sub-problem으로 해서 recursively하게 문제를 해결하는 방식이다.

풀어서 쓰면, 배열의 왼쪽부터는 pivot보다 큰 값을 찾고, 배열의 오른쪽부터는 pivot보다 작은 값을 찾아서 이 둘의 위치를 바꾼다음 이 작업을 왼쪽에서 찾은 값의 index와 오른쪽에서 찾은 값의 index가 엇갈릴 때 까지 반복한다. 즉 pivot의 왼쪽에는 pivot보다 작은 값을 모으고, pivot의 오른쪽에는 pivot보다 큰 값을 모으는 방식이다. 

아래의 예시로 이해하면 빠를 수 있다.
3 7 8 1 5 9 6 10 2 4 가 있고, 기준값을 3으로 정하면 (일반적으로 배열의 첫 값을 기준값으로 정한다). 왼쪽에서는 7, 오른쪽에서는 2가 찾아지고

3 7 8 1 5 9 6 10 2 4 $\rightarrow$
3 2 8 1 5 9 6 10 7 4 이 된다. 계속해서 반복하면
3 2 8 1 5 9 6 10 7 4 $\rightarrow$
3 2 1 8 5 9 6 10 7 4

이제 여기서는 왼쪽에서는 8 (index = 3). 오른쪽 에서는 1 (index = 2) 가 찾아지는데  index가 엇갈린다. 이때는 왼쪽에 있는 값 (작은 값)과 pivot값을 바꾸어 준다.

1 2 3 8 5 9 6 10 7 4 이제 1과 3은 정렬이 된 값으로 두고, 3을 기준으로 왼쪽과 오른쪽의 두 집합으로 나누어서 정렬을 반복한다.

1 2 3 8 5 9 6 10 7 4 에서 3을 기준으로 왼쪽 집합에서는 1이 오른쪽 집합에서는 8이 pivot이 되고, 왼쪽집합(={1,2})에서는 pivot인 1보다 큰값인 2만 찾아지므로 2도 정렬이 된 값으로 고정한다. 오른쪽 집합(={8 5 9 6 10 7 4}) 에서는 다음과 같이 정렬이 된다.

1 2 3 8 5 9 6 10 7 4 $\rightarrow$
1 2 3 8 5 4 6 10 7 9 $\rightarrow$
1 2 3 8 5 4 6 7 10 9 여기서 이제 10과 7이 선택 되는데 index가 왼쪽에서 찾은 값과 오른쪽에서 찾은값이 또 엇갈렸으므로 pivot값 (여기서는 8)과 작은값 (7)을 바꾸어준다.

1 2 3 7 5 4 6 8 10 9 이제 다시 8을 기준으로 왼쪽 오른쪽의 두 집합 ({7 5 4 6}, {10 9}) 으로 나누어 짐을 확인할 수 있다. 이제 7과 10을  각각의 pivot으로 잡고 마찬가지로 정렬을 수행하면 정렬이 마무리 된다.

이제 이를 c++로 구현해보자

#include <iostream>
using namespace std;

int array[10] = {3, 7, 8, 1, 5, 9, 6, 10, 2, 4};    
int start = 0, end = 9;

// 정렬을 수행하고 pivot값을 새로잡은 후 
// 왼쪽과 오른쪽을 나누어 다시 정렬 수행 -> 재귀함수의 형태로 구현 하는 것이 바람직
void quickSort(int* array, int start, int end){
    int pivot = array[start];  
    int i=start, j=end, temp=0;

    //집합의 원소가 1개일땐 정렬이 필요 없으므로 return
    if(start>=end) return;

    //왼쪽에서 선택된 index(i)와 오른쪽에서 선택된 index(j)가 엇갈리기 전까지 반복
    while(i <= j){
        //array index를 증가시키면서 pivot값 보다 큰 값의 index 찾고 
        while(i <= end && array[i] <= pivot)	i++;        
        //array index를 감소시키면서 pivot값 보다 작은 값의 index를 찾는다.
        while(j > start && array[j] >= pivot)	j--;

        //두 값을 찾았으면 서로 교체 해주기
        if(i<j){
            temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }

     	//i와 j가 엇갈리면 pivot 값과 index j의 값을 바꿈
        else{
            array[start] = array[j];
            array[j] = pivot;
        }
    }

    //이제 index j를 기준으로 왼쪽 집합은 array[j]보다 작은값,
    // 오른쪽 집합은 array[j]보다 큰 값만 모여 있게 된다.
    // 이 두집합을 각각 다시 정렬해주면 quick sort 완성
    quickSort(array, start, j-1);
    //start가 end보다 크게되면 맨위 if(start>=end) return 에 해당되어서 위의 quickSort가 종료되고 
    //아래의 quickSort로 넘어감
    quickSort(array, j+1, end);
 }

int main(){
    quickSort(array, start, 9);
    
    for(int i=0; i<10; i++){
        cout << array[i] << " ";
    }
}