Quick Sort

본 문서는 2021년 12월 30일 에 작성되었습니다.

Dev 알고리즘 시리즈의 Sort 알고리즘 파트에서는 다음을 알아보았습니다.

1. Selection Sort
2. Insertion Sort
3. Merge Sort
4. Heap Sort

이들은 모두 기본 행렬 혹은 Node 가 추가된 기본 행렬 기반의 숫자 비교 정렬 알고리즘입니다.그리고 Quick Sort 는 마지막으로 배울 숫자 비교 알고리즘입니다.

Quick Sort 위한 프로시저

만약 당신이 Merge Sort를 자세히 읽었다면 분할 정복 과정 이 무엇인지 알 것이라고 생각한다.

Quick Sort 또한 분할 정복 과정으로 그 단계는 다음과 같다.

1. 분할 | A[p, ..., r] 을 분할할 기준값 인덱스 q를 구하고 A'[p, ..., q-1] 와 A''[q, ... , r] 에 각각 q보다 작은 값과 큰 값을 분할(재배치) 한다. 이 때, A' 와 A'' 는 공배열이 될 수 있다. A'와 A'' 는 구분상의 편의로 구분했을 뿐, 실제로는 하나의 배열일 뿐이다.
2. 정복 | Quick Sort 를 재귀 호출하여 각 부분배열 A' 와 A'' 을 정렬한다.
3. 결합 | 1,2 번이 정상적으로 완료 되었다면 이미 A[p, ... , r] 은 정렬되어 있으므로, 별도로 합치는 과정을 할 필요가 없다.

위 과정을 하기 위한 프로시저는 다음과 같다.

1. PARTITION | 임의의 인덱스를 정하고 이를 기준으로 파티션을 나눈다.
2. QUICK SORT | 배열을 정렬한다.

Partition

# Partition 의사코드

PARTITION (A, p, r)

x = A[r]
i = p-1

for j=p to r-1
   if A[j]<=x
      i=i+1
      exchange A[i] with A[j]
exchange A[i+1] with A[r]
return i+1

Quick Sort

# Quick Sort 의사코드

QUICK SORT (A, p, r)

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

결론

Qucik Sort 의 핵심은 분할(Partition) 에 있다.
최악의 경우 O(n^2) 이지만 최적의 경우 O(n lg n) 인 Quick Sort 는 내부정렬로써 추천된다. 하지만, 어떤 임의이 입력값의 분포도 를 예측할 수 없다면 이 방법은 최악의 선택일 수 있다.

이러한 경우 성능의 기댓값으로 Randomized Partition 을 통한 Quick Sort 가 좋은 해결책이 될 수 있다. 물론 입력값이 충분히 크다는 전제가 추가로 필요하다

Randomized Quick Sort 를 위한 프로시저

Radomized Quick Sort 는 다음과 같은 두가지 방법으로 구현할 수 있다.

1. 명시적으로 입력을 뒤섞음
2. 다른 무작위 추출 이라는 랜덤화 기법을 사용

다만 주의해야 할 점은,
각 프로그래밍 언어마다 지원하는 무작위 추출법은 정말로 다양하고
무작위 추출이라고는 하지만 실제로 균등한 확률을 가지고 있지는 않다느 점이다.
표준분포상 중간값을 뱉을 확률이 높을 수도 있다

Randomized Partition

# Randomized Partition 의사코드

RANDOMIZED PARTITION (A, p, r)

i=RANDOM(p, r)
exchange A[r] with A[i]
return PARTITION(A, p, r)

Randomized Quick Sort

Randomized Quick Sort 의사코드

RANDOMIZED QUICK SORT (A, p, r)
if p,r
   q=RANDOMIZED PARTITION (A, p, r)
   RANDOMIZED QUICK SORT (A, p, q-1)
   RANDOMIZED QUICK SORT (A, q+1, r)

결론

Quick Sort 의 성능을 끌어올리려면 한가지 제약 조건이 필요하다.
입력값이 균일하여 Partition 프로시저를 효율적으로 수행할 수 있을 것

그렇지 못한 경우 Randomized Quick Sort 를 사용하지만 이 또한 다음의 제약조건이 붙는다.
입력값의 크기가 충분하게 클 경우에는 무작위 추출 등을 사용해 랜덤화 Partition 프로시저 수행할 것

이렇듯,
특별한 상황에서 안정적으로 높은 성능을 보여주는 비교 정렬 이기 때문에,
Heap Sort 처럼 특정 조건을 만족했는가 여부를 따져보고 도입하면 좋을 것 같다.