정렬(Sorting)

퀵 정렬(quick sort)

퀵 정렬(quick sort)

퀵 정렬은 일단 정렬되지 않은 두 개의 리스트로 분할하는데, 이 때 어떤 pivot 원소를 중심으로 한 쪽은 pivot 원소보다 작은 값들이 다른 쪽에는 pivot 원소보다 큰 값이 들어 있다. 각 리스트에서는 퀵 정렬을 다시 적용하는 재귀적 방식으로 정렬을 진행한다.

pivot 원소는 리스트에서 임의의 원소를 결정할 수 있는데, 편의상 리스트의 처음 값으로 정하기로 한다. 다른 방법으로는 median-of-three가 있는데, 이 것은 처음, 중간, 끝에 있는 원소의 중간값으로 정하는 방식이다.

아래 예를 통하여 퀵 정렬 알고리즘이 동작하는 방식을 살펴보기로 한다.

퀵 정렬의 분석

퀵 정렬에서 pivot 원소를 선택하는 것이 알고리즘의 실행 시간에 많은 영향을 미친다. 가장 바람직한 것은 중앙값을 pivot 원소로 선택하여 리스트 분할시 양쪽이 균등하게 분할되는 것이다. 이 경우는 시간 복잡도는 다음과 같이 구할 수 있다.

[eqn: T(n) le 2 cdot T(n/2) + cn = O(n log n)]

최악의 경우는 이미 정렬된 리스트를 퀵 정렬을 이용하여 정렬하는 경우이다. 이미 정렬되어 있는 상황에서 맨 앞의 원소를 pivot 원소로 선정하면 한 쪽 리스트는 크기가 [eqn: 0]이고 다른 쪽은 크기가 [eqn: n-1]이 된다. 따라서 시간 복잡도는 다음과 같이 나타난다.

[eqn: T(n) le T(n-1) + cn = O(n^2 )]

퀵 정렬의 평균 시간 복잡도는 [eqn: O(n log n)]임을 보일 수 있다. 실제 구현에서도 다른 정렬 알고리즘보다 빠르다고 알려져 있다.

퀵 정렬에서는 재귀 호출을 위한 스택이 필요하다. 스택의 크기는 최악의 경우 [eqn: O(n )]이고, 최상의 경우 [eqn: O(log n )]이다.

참고. 중간값을 [eqn: O(n )] 시간에 찾을 수 있는 알고리즘이 있다. 퀵 정렬에서 이 알고리즘을 이용하여 중간값을 찾은 다음 이것을 pivot 원소로 이용하면 최악의 경우 시간 복잡도는 [eqn: O(n log n )]이 된다. 그러나 중간값을 찾는 알고리즘이 구현하기 복잡하고 [eqn: n]이 아주 크지 않을 때는 상대적으로 시간이 많이 걸리기 때문에 실제 사용하고 있지 않다.