Quick Sort(퀵 정렬)

이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리한 내용입니다.

Quick Sort(퀵 정렬)

퀵 정렬은 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.

n개의 데이터를 정렬할 때, 최악의 경우에는 O(n^2)번 비교를 수행하고, 평균적으로 O(nlogn)번의 비교를 수행한다.

퀵 정렬은 분할 정복 방법을 통해 리스트를 정렬한다.

1. 리스트 가운데 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.

2. 피벗 앞에는 피벗보다 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.

3. 분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때 까지 반복된다.

재귀 호출이 한 번 진행 될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

분할정복법

분할 : 배열의 다음과 같은 조건이 만족되도록 두 부분으로 나눈다.

elements in lower parts    <=    elements in upper parts

정복 : 각 부분을 순환적으로 정렬한다.

합병 : noting to do

예시

정렬할 배열이 주어짐, 마지막 수를 기준(pivot)으로 삼는다.

[31, 8, 48, 73, 11, 3, 20, 29, 65, 15]

기준보다 작은 수는 기준의 왼쪽에 나머지는 오른쪽에 오도록 재배치(분할) 한다.

[8, 11, 3, 15, 31, 48, 20, 29, 65, 73]

기준의 왼쪽과 오른쪽을 각각 순환적으로 정렬한다.(정렬 완료)

[3, 8, 11, 15, 20, 29, 31, 48, 65, 73]

의사코드

Quick Sort(A[], p, r) {
if(p < r) then {
q = Partition(A, p, r);
Quick Sort(A, p, q-1);
Quick Sort(A, q+1, r);
}
}

Partition(A[], p, r) {
배열 A[p...r]의 원소들을 A[r]을 기준으로 양쪽으로 재배치 하고
A[r]이 자리한 위치를 return 한다.
}

Quick Sort(A[], p, r) {
if(A[j] >= x) {
j <- j+1;
} else {
i <- i+1;
exchange A[i] and A[j];
j <- j+1;
}
}

Partition(A[], p , r) {
x <- A[r];
i <- p-1;
for j <- p to r-1
if(A[j] <= x ) then
i <- i+1;
exchange A[i] and A[j];
exchange A[i+1] and A[r];
return i+1;
}

시간복잡도

최악의 경우

항상 한 쪽은 0개, 다른 쪽은 n-1개로 분할되는 경우

이미 정렬된 입력 데이터(마지막 원소를 피봇으로 선택하는 경우)

T(n) = T(0) + T(n-1) + O(n)

= T(n-1) + O(n)

= T(n-2) + T(n-1) + ... + O(n-1) + O(n) ...

= O(1) + O(2) + ... + O(n-1) + O(n)

= O(n^2)

최선의 경우

항상 절반으로 분할되는 경우

T(n) = 2T(n/2) + O(n)

= O(nlogn)

평균 시간복잡도

N의 리스트를 정렬하는데 걸리는 시간을 , c는 임의의 상수라 하고, 리스트가 두 개의 거의 같은 부분집합으로 나뉜다고 가정하여 얻은 평균 시간복잡도는 다음과 같다.

소스 코드(Java)