퀵소트(quick sort) 알고리즘

퀵소트(quick sort) 알고리즘

정렬 알고리즘 중 평균적으로 O(NlogN)으로 알려져 있는 Quick sort에 대해 알아보자.

1. 기본 아이디어

기본적으로 O(N^2)으로 정렬하는 알고리즘(Ex : 버블정렬)은 바꾸는 기준이 순회를 하면서 바뀌어 지면서, 일반적으로 for문의 중첩으로 O(N^2)의 복잡도를 가지게 된다. 하지만 퀵소트 알고리즘은 직관적으로 보았을 때, 비교를 반씩 줄여나가면서 해보자! 라는 생각으로 접근을 하면 이해하기 좋을 것 같다. 즉 재귀를 이용한 분할정복 알고리즘이다. 

기본적인 아이디어는 상당히 쉽다. 특정한 기준을 Pivot 이라고 부르고 이 pivot을 기준으로 pivot보다 작으면 왼쪽으로, pivot보다 크면 오른쪽으로 이동한다. 

기본적인 아이디어를 바탕으로 제대로 동작하는지 살펴보자.

이렇게 처음부터 하나씩 비교를 하게 되고, pivot을 기준으로 작은것은 왼쪽, 큰것은 오른쪽으로 이동을 시켰다. 이렇게 진행을 하게 되면 결과적으로 우리가 확신할 수 있는 것이 있다. 

이 과정을 거치고 나면 직관적으로 우리는 5보다 왼쪽에 있는 것과 5보다 오른쪽에 있는 값들을 섞을 필요가 없다는 것을 알 수있게 된다. 왜냐하면, 우리가 5보다 작은 것들은 왼쪽, 5보다 큰것들은 오른쪽으로 두었기 때문에, 각각 좌,우를 나누어서 다시 이 과정을 반복하면 된다.

편의상 왼쪽편 [1,4,2,3] 만 정렬하겠다. 실행과정을 계속 이어나가보면.

이렇게 결과적으로 정렬이 마무리가 되었다. 

실제 전체를 다 해보면, 연산 횟수를 간단하게 순회하는 횟수라고 생각해보면, 대충 20번 정도 하면 정렬이 마무리 되는 것으로 보인다.

즉 버블 정렬의 경우 무조건 64번의 순회를 해야되는 것이 비해 상당히 빨라졌다고 볼수 있다.(참고.퀵소트의 최악의 경우는 O(N^2)이다.)

다시 정리를 해보면 퀵정렬의 기본 아이디어 자체는

1. pivot(기준점)을 선정하고

2. pivot을 기준으로 작으면 왼쪽, 크면 오른쪽으로

3. 정렬이 될 때 까지 구별한 왼쪽과 오른쪽을 나누어서 분할처리한다.

2. 실제 구현

대충 어떻게 동작하는 지는 알고 있는데 이걸 써먹을러면 코드로 작성을 해야하는데, 왼쪽과 오른쪽으로 나누어서 작동을 해야 하는데, Swap을 하는 과정이 약간 복잡해 지면서 머리가 아파오기 시작한다. 또한 Pivot을 중앙으로 잡을지 첫번째로 잡을 지 고민이 되면서 또다시 머리가 아파오기 시작한다. 

기본아이디어에 바탕을 둔 실제 구현의 동작과정은 아이디어는 똑같지만 진행과정은 구현과 성능을 고려해서 약간 달라지게 된다.

완벽한 퍼포먼스와 군더더기 없이 퍼펙트 한 구현은 나도 할수 없지만, 일반적으로 구현하는 방식에 대해 살펴보겠다.

우선 편의를 위해서 Pivot과 j는 첫번 째로 두었다. i는 j+1로 두었다. 

우리는 Pivot을 기준으로 왼쪽과 오른쪽이라는 기본 아이디어를 구현 할 것이다.  

즉 i와 Pivot을 비교하여서 작으면 Pivot의 왼쪽으로 보내야 한다. 그 왼쪽으로 보내는 것의 편의를 위해 j라는 변수를 설정해 놓은 것이다.

결과적으로 i를 끝까지 순회하면서, Pivot보다 작으면 j를 한칸 오른쪽으로 이동시키고 i와 교환을 하면 된다.

이렇게 말로하면 좀 이해가 안갈것이다. 동작 과정을 통해서 제대로 작동하는지 확인해 보자.

집고 넘어가자면

Pivot : 기준

i : 비교 할 값

j : 교체 할 값

실제 4~7 까지 pivot인 5와 비교를 하면 결과적으로 바뀌어 지는 수가 없게 된다. 그렇다 우리는 결과적으로 마지막 과정을 하나 빼먹었다.

Pivot과 j를 교체해보자.

결과적으로 1과 5(Pivot과 j)와 교환을 하게 되면 Pivot인 5를 기준으로 왼쪽은 5보다 작은 수, 오른쪽은 5보다 큰 수만 존재하게 된다.

뭐지???????????????????라는 생각을 할수도 있다.

우리가 위에서 동작한 과정을 다시 생각해 보면서 j의 존재를 다시 각인시켜보자.

j란 것은 처음에 Pivot으로 시작을 하게 된다. 즉 이땐 Pivot과 같은 값이라는 것이 보장된다.

그 이후에 pivot과 i와 비교를 하게 되면서, i가 pivot 보다 크다면 j는 그대로 유지가 될것이다.

i가 pivot보다 작게 된다면, j는 오른쪽으로 한칸 이동을 하게 되면서 j와 i가 교체를 하게 된다. 

이때 j의 값은 무조건 i보다 같거나 작을 것이고, [0 ~ j] 구간의 경우는 무조건 pivot보다 같거나 작다는 것을 보장할 수 있다.

왜냐면, pivot보다 작은 i 일때 j의 값과 교환을 하기 때문이다.

간단하게 에를 들어보면

5 6 7 1 2 를 정렬을 해 보자

5 6 7 1 2  => 6과 7은 pivot 5보다 크기 때문에 그냥 지나치고 1을 만났을때 pivot 5보다 작기 떄문에 j++, i,j 값 교체

j       i

5 1 7 6 2  =>2는 pivot 5보다 작기 때문에 j++, i,j 값 교체

   j       i

5 1 2 6 7  => 마지막으로 pivot인 5와  j인 2를 교환해야 한다.

     j     i

2 1 5 6 7    => 결과적으로 5를 기준으로 왼쪽은 5보다 작은값, 오른쪽은 5보다 큰값이 존재하게 된다.

이렇게 되면 실제 구현을 할 때의 동작 과정을 어느정도 이해했다고 본다. 

실제 코드는 아래 첨부해 두었다.

#include <cstdio>
 
void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}
 
 
void quickSort(int left,int right, int* data) {
    int pivot = left;
    int j = pivot;
    int i = left+1;
 
    if (left < right) {
        for (; i <= right; i++) {
            if (data[i] < data[pivot]) {
                j++;
                swap(&data[j], &data[i]);
            }
        }
        swap(&data[left],&data[j]);
        pivot = j;
 
        quickSort(left, pivot-1,data);
        quickSort(pivot+1, right, data);
    }
 
}
 
int main() {
 
    int arr[5] = { 5,4,3,2,1 };
    quickSort(0, 4, arr);
    for (int i = 0; i < 5; i++) printf("%d ",arr[i]);
 
    return 0;
}

소스코드 : 깃허브