[알고리즘] 퀵정렬(Quick sort)이란?

1. 퀵정렬이란?

Quick sort

퀵정렬(Quick sort)란, 분할과 정복(divide and conquer)의 개념을 이용하여 정렬하는 알고리즘으로 이름대로 평균적으로 가장 빠르게 작동하는 알고리즘이라고 할 수 있다. 배열 중 숫자를 하나 선택하고, 그 숫자를 기준으로 큰 수와 작은 수를 나누는 방식으로 진행된다. 

퀵 정렬이 진행 방식은 다음과 같다. 

1. 배열에서 원소를 하나 선택한다. 이 때 선택되는 숫자는 Pivot이라고 부른다.
2. 피벗이 되는 숫자를 기준으로 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 나눈다.
3. 분할되는 배열의 크기가 1 이하가 될 때까지 분할된 두 부분 내에서 또 다시 1~2의 과정을 반복한다. 
4. 분할된 부분 배열들을 합쳐 정렬된 배열을 최종 생성한다.

2. 퀵정렬의 예시

{2,8,7,1,3,5,6,4}가 있을 때, 이들을 퀵정렬로 정렬한다고 생각해보자.

Pivot은 첫 번째, 가운데, 마지막 등 다양한 위치에 있는 숫자가 될 수 있지만 이 예시에서는 마지막 숫자인 4로 설정한다. 

그 뒤 배열의 앞에서부터 하나씩 확인하며 Pivot으로 설정된 4보다 작은 지, 큰 지를 비교한다. 맨 앞의 2와 같은 경우는 4보다 작으므로 왼쪽으로 분류된다. 이 경우 작은 숫자들의 모음이 어디까지인지를 표시하는 파티션(사진에서는 굵은 테두리)의 위치를 기억하게 된다. 

작은 숫자를 만났을 때와 마찬가지로, Pivot보다 큰 값을 만났을 때에도 어디까지가 큰 수의 모음인지를 표시하는 파티션을 추가하게 된다. 

이후 이 파티션을 기억해, 더 큰 수가 나타나면 구분하는 파티션의 위치를 업데이트 하는 식으로 진행한다.

참고로 위에서의 1과 같이 큰 수들로 분류된 부분을 넘어 작은 것들의 모음으로 가야하는 경우, 작은 수 모음과 큰 수 모음의 경계에 있는 8과의 자리를 바꾸는 방식으로 진행한다. 이렇게 하는 경우 1과 8만 바꾸면 되기 때문에 간편해진다. 

큰 수의 집합과 작은 수의 집합 내에서의 숫자 순서는 상관하지 않고, 단순히 Pivot보다 비교하려는 값이 큰 지, 작은 지만 비교한다. 

pivot을 제외한 전체 원소를 한 번씩 비교하면 이렇게 정렬이 되고, 

작은 수 집합과 큰 수 집합이 나뉘는 파티션에 Pivot값이 들어가게 된다. 이렇게 한 번이 완료되고 나면, 선택된 Pivot값은 배열 내에서 있어야 할 위치에 있게 된다고 할 수 있다. 이후 왼쪽, 오른쪽으로 나뉜 두 배열 내에서 위와 같은 방식이 동일하게 진행하며 각 원소들이 순서대로 정렬되게 된다. 

3. 퀵정렬의 pseudo code

QUICKSORT(A,p,r)
if p < r
	q = PARTITION(A,p,r)
    QUICKSORT(A,p,q-1)
    QUICKSORT(A,q+1,r)

배열 A에서 p번째부터 r번째까지를 정렬한다. 만약에 배열 A의 원소가 1개라서 p == r이라면 그냥 해당 값을 return 한다. 

또한 파티션을 하게 되면 그 값의 결과로 Pivot값이 들어가게 되는 q라는 위치가 생기며, 그 값을 기준으로 QUICKSORT를 재 진행하는 식으로 진행된다.

참고로 PARTITION의 pseudo code는 다음과 같다. 

PARTITION(A,p,r)
x = A[r]
i = p-1 # 왼쪽 파티션의 마지막 위치
for j = p to r - 1 # j : 오른쪽 파티션의 마지막 위치
	do if A[j] <= x # 하나씩 확인하면서 x보다 작으면
    	then i = i+1 # 왼쪽 파티션을 update
        	exchange A[i] <-> A[j]
exchange A[i+1] <-> A[r] # 왼쪽 파티션의 마지막 위치에 Pivot 값이 들어가야 하니 바꿔주기
return i + 1 # Pivot값의 위치 return

4. 공간복잡도

in-plcae알고리즘으로 별도의 추가 메모리가 필요하지 않으므로 공간 복잡도는 O(n)이다. 

5. 시간복잡도

퀵소트의 시간 복잡도는 보통 O(nlogn)을 가진다. 내가 어떤 수를 Pivot으로 설정하던 나머지 요소들을 모두 보아야 하기 때문에 best case, average case모두 동일하게 O(nlogn)의 시간 복잡도를 가진다. 하지만 최악의 경우에는 O(n^2)의 복잡도를 가지게 되는데, 이 때에는 Pivot이 항상 최소 또는 최대로만 선택되는 경우에는 나누어서 실행하지 못하고 Pivot을 제외한 나머지를 대상으로 다시 실행하게 되기 때문이다.