Quick sort 소개

Quick sort도 divide and conquer 방식을 따르는 알고리즘 중 하나이다.

(Divide) 우선 배열 중 하나의 요소를 pivot으로 두고, pivot을 기준으로 배열을 두 개의 subarrays로 나눈다.
여기서 pivot보다 작거나 같은 요소는 왼쪽 subarray로, pivot보다 큰 요소는 오른쪽 subarray에 둔다.

(Conquer) Quick sort의 재귀 호출로 두 개의 subarray를 정렬한다.  

(Combine) 이제 합칠 때, subarray는 이미 정렬되어 있으므로, 합치기 위해 더 필요한 작업은 없다.  

 

이 과정을 슈도 코드로 확인해보자.

Quicksort(A,p,r) // A는 배열, p는 start index, r은 end index
	if p<r
    	q = Partition(A,p,r) // 배열과 start, end index를 넣어서 pivot q를 구함
        Quicksort(A,p,q-1)
        Quicksort(A,q+1,r)  // 여기서 pivot은 매개변수에서 제외함 (주의)

 

partition 이후, 나뉜 배열은 이런 모습을 하고 있을 것이다.

보통 pivot은 가장 첫번째 요소를 선택하거나, 마지막 요소를 선택한 후 정렬한다.

 

 

아직 어떤 느낌인지 잘 안와닿을 수 있다. 예시를 보자.
( p: start index, r: end index, i: index of the left subarray, j: index of the right subarray )

우선 가장 마지막 요소를 pivot으로 잡았다. 이제 우리는 이 pivot을 기준으로 배열을 순회하기 시작한다.

첫 번째 요소 2가 pivot 4보다 작기 때문에 2를 왼쪽 subarray에 저장한다.

두 번째 요소 8은 pivot보다 크기 때문에 오른쪽 subarray에 저장한다.

이런식으로 반복해서 더 이상 정렬할 요소가 없을 때, i인덱스의 오른쪽에 pivot을 옮기고 순회를 마친다.

 

Quick sort에는 두 가지 case가 존재한다.
Case 1은 pivot이 element보다 작은 경우.
Case 2는 pivot이 element보다 크거나 같은 경우.

Case 1의 경우라면 j번째 인덱스만 다음으로 옮겨갈 뿐일테고,

Case 2의 경우라면 i+1과 j의 element들을 swap할 것이다.

아래는 위 과정의 partition 슈도코드이다.

Partition(A,p,r) //p는 시작, r은 끝 index
x = A[r]  // pivot 설정
i = p - 1
    for j = p to r-1
    	if A[j]<=x          // Case2
        	i = i+1
            swap A[i],A[j]
         swap A[i+1],A[r]
return i+1

 

이것은 한 번의 회차일 뿐이고 전체적인 흐름을 본다면 다음과 같다.

quick sort로 잘게 쪼개다 보면, 나중엔 단지 다음 index의 노드를 연결하는 것으로 바로 전체 배열이 정렬된다.

 

그럼 이렇게 두 부분으로 나뉘어진 subarray에서 시간복잡도는 어떻게 될까?

위 그림처럼 best case와 worst case를 예상해볼 수 있다. 같은 이유로 모든 array가 이미 정렬되어 있는 경우와, 모든 array의 요소가 같은 값을 가질 경우도 worst case의 unbalanced하게 나뉘어지게 되므로 시간복잡도는 n^2이 될 것이다.

그래서 우리는 밸런스가 무너지지 않도록 pivot의 위치를 잘 선정해야 할 필요가 있다. 이런 이유 때문에 보통 quick sort에선 아까 말했던 첫번째 또는 마지막 요소를 pivot으로 잡기 보단, 배열의 요소 중 하나를 무작위로 뽑아서 pivot으로 선정한다.

여기서 quick sort를 더 개선할 수 있다. 배열의 요소들의 값들 중 중간값을 찾아서 pivot으로 선정하는 것이다. 이 때, subarray의 크기가 n이라면 O(n)의 시간이 필요하다.

다른 방법으로는 n개를 scan할 필요 없이, 무작위로 3개 정도의 요소를 선택한 다음 그 중에서 중간값을 pivot으로 선택하는 방법도 있다.