퀵 정렬 (Quick Sort)

퀵 정렬 (Quick Sort)

퀵 정렬, 말 그대로 빠른 정렬입니다.

평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법으로 퀵 정렬도 합병 정렬처럼 분할-정복(Divide & Conquer) 방식을 사용합니다.

하지만, 합병정렬과는 다르게 퀵 정렬은 리스트를 비균등하게 분할합니다.

1. 리스트 안에 한 요소를 피벗으로 선택한다. 대체로 첫 번째 요소를 피벗으로 선정합니다.

2. 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로, 큰 요소들은 오른쪽으로 옮깁니다.

3. 피벗을 제외한 왼쪽과 오른쪽의 리스트들을 대상으로 1~2의 과정을 반복해 정렬을 완료합니다.

위 그림의 마지막 상태는 피벗 5를 기준으로 왼쪽 리스트는 피벗보다 작은 데이터, 오른쪽 리스트는 피벗보다 큰 데이터들로 구성되어 리스트가 분할된 것을 보여줍니다.

이 상태에서 피벗 5는 이미 제 위치에 있음을 알 수 있습니다.

다음으로 왼쪽 리스트와 오른쪽 리스트들을 각각 다시 퀵 정렬하여 정렬을 마무리 짓습니다.

퀵 정렬의 특징

퀵 정렬은 빠른 정렬로 평균적으로 O(nlog 2n)의 시간복잡도를 가지게 됩니다. 하지만 최악의 경우 O(n^2)의 시간 복잡도를 가지게 됩니다.

또한, 퀵 정렬은 추가 메모리 공간을 필요로 하지 않으며 정렬된 리스트에 대해서는 오히려 수행시간이 더 많이 걸리는 단점도 있습니다.

- 이러한 불균형 분할을 방지하기 위해 피벗을 선택할 때 단순히 리스트의 왼쪽 데이터를 사용하는 대신 리스트 내의 중간 값을 피벗으로 선택하기도 합니다. (왼쪽, 오른쪽, 중간의 세 값중 중간 값을 택해서 선택하는 방법을 많이 사용합니다.)

퀵 정렬의 구현

출처 : http://wonjayk.tistory.com/222