32. Quick Sort

병합 정렬은 $\Theta(n\text{ lg }n)$의 시간복잡도를 갖지만 메모리 사용량이 너무 많다는 문제가 있다. 이러한 문제가 발생하지 않으면서 병합 정렬과 같은 평균 시간복잡도를 갖는 정렬 방법으로 퀵 정렬(Quick Sort)이 있다. 퀵 정렬은 한 원소의 위치를 고정하고 앞뒤 원소들을 같은 방법으로 정렬하는 분할 정복 기법의 일종이며, 평균적인 상황에서 최고의 성능을 보이지만 최악의 시간복잡도는 $\text{O}(n^2)$라는 문제점이 존재하며, 동일한 값이 여러 개 존재하는 경우 정렬 과정에서 상대적인 순서가 바뀔 수 있다.

 

퀵 정렬의 과정을 요약하면 다음과 같다.

 

1. 피벗을 고른다.

2. 피벗보다 뒤에 나와야 하는 첫 번째 원소 $a_i$를 찾는다.

3. 피벗보다 앞에 나와야 하는 마지막 원소 $a_j$를 찾고 인덱스 $i$와 $j$를 비교한다.

4. $i < j$인 경우 $a_i$와 $a_j$를 교환하고 2번으로 되돌아간다.

5. $i > j$인 경우 피벗과 $a_j$를 교환하고 피벗의 앞과 뒤를 같은 방법으로 정렬한다.

 

어떤 경우는 $a_i$나 $a_j$가 존재하지 않을 수도 있는데, 이것은 피벗이 정렬하는 범위에서 가장 앞 또는 가장 뒤에 나와야 한다는 말이므로 따로 처리를 하면 된다.

 

다음은 퀵 정렬을 시뮬레이션한 것이다.

퀵 정렬의 성능이 나빠지지 않게 하려면 피벗을 잘 선택하는 것이 중요하다. 만약 피벗의 앞에 오는 원소와 뒤에 오는 원소의 개수 차이가 크다면 피벗을 잘 선택하지 못한 것이다. 즉 정렬할 구간에서 중간 정도의 위치에 나오는 값을 선택하는 것이 좋지만, 원소들의 배열 상태에 관계없이 이런 피벗을 잘 선택하는 것이 어렵기 때문에 피벗을 잘 선택하기 위한 여러 가지 방법들이 연구되고 있다. 주요 컴파일러에서는 구간에서 몇 개의 값을 고른 뒤 그것들의 중앙값을 피벗으로 하는 방법을 사용한다.

 

→ solved.ac tag: sorting