알고리즘 7장 - 정렬 문제 : 퀵 정렬 -

알고리즘 7장

- 정렬 문제 : 퀵 정렬 -

 

퀵 정렬은 크기가 커서 풀기 어려운 하나의 문제를 크기가 작아서 풀기 쉬운 여러 개의 문제로 바꾸어서 푸는 방법을 사용한다. 이런 방법을 divide-and-conquer paradigm라고 한다. 이를 수행하기 위해 Partitioning을 사용하여 정렬을 한다. Pivot element를 사용하여 Pivot element 왼쪽에는 Pivot 보다 작은 수들을 오른쪽에는 Pivot 보다 큰 값을 가지도록 정렬을 한다. Pivot을 계속 설정하여 위의 과정을 반복하여 수행하면 배열이 오름차순으로 정렬이 되게 된다. 퀵 정렬의 경우 Pivot을 어떻게 잡아서 Partitioning을 수행하는지가 매우 중요한 요건이라고 할 수 있다.

예를 들어 생각을 해보자. <2, 8, 7, 1, 3, 5, 6, 4> 라는 배열이 있다. 맨 마지막의 수인 4를 Pivot element로 두었다고 생각하자. 그러면 앞에 있는 수들 중에서 4의 값보다 작으면 왼쪽으로 크면 오른쪽으로 배열을 맞추게 된다. <2, 1, 3>의 수는 4의 왼쪽으로 정렬시키고 <8, 7, 5, 6>은 4의 오른쪽으로 정렬을 시킨다. 이를 계속 반복하여 왼쪽과 오른쪽에 대한 정렬을 다시 수행하는 것이다.

Pseudo code를 사려보면 배열과 첫 번째 index, 마지막 index를 parameter로 받게 된다. 이 후 Partitioning을 하는데 q라는 Pivot element를 잡게 된다. 이를 통해 Partitioning이 된 배열의 경우 Pivot을 기준으로 왼쪽과 오른쪽이 나누어진 형태로 배열이 정렬될 것이다. 그러면 왼쪽과 오른쪽에 대한 퀵 정렬을 다시 진행해서 단계적으로 진행하여 퀵 정렬을 하는 배열이 하나의 값만 가질 때까지 진행하게 된다.

퀵 정렬의 경우 수행 시간이 Pivot element를 어떻게 잡느냐에 따라 다르게 된다. 이 때 Balanced partitioning과 Unbalanced partitioning으로 나눌 수 있게 된다. Balanced partitioning은 각 하위 문제의 크기가 기존 문제의 크기의 절반정도가 되도록 나누어지는 경우를 말한다. Pivot element의 값이 배열의 전체 값들에 평균 지점에 해당하는 경우이다. 이 때는 O(nlgn)의 수행시간이 소요되게 된다. unbalanced partitioning은 Pivot element에 의해 1개와 n-1개로 나누어지는 경우를 말한다. 그렇게 되면 O(n^2)의 수행 시간이 소요되게 된다.