[Algorithm] 퀵정렬
1. 무엇인가?
리스트에서 피벗(하나의 요소)을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽에 정렬한다.
정렬된 두 부분에서 다시 피벗을 설정하고, 작은 값은 왼쪽, 큰 값은 오른쪽에 정렬한다.
위 과정을 더 이상 리스트를 분할할 수 없을 때까지 진행한다.
2. 어떻게 사용하는가?
1. 리스트 내부에서 기준이 될 피벗(요소)을 선택한다.
2. 피벗을 기준으로 피벗보다 작은 요소들은 피벗의 왼쪽으로 옮기고, 피벗보다 큰 요소들은 피벗의 오른쪽로 옮긴다.
3. 피벗을 제외한, 왼쪽의 부분 리스트, 오른쪽의 부분 리스트를 같은 방식으로 다시 정렬한다.
분할된 부분 리스트에 대하여 재귀 호출을 이용하여 정렬을 반복한다.
4. 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.
<피벗에서 가장 중요한 부분 : Pivot Selection>
퀵정렬의 경우 평균적으로 nlogn의 시간복잡도를 가지지만 피벗 설정에 따라, 최악의 경우 시간복잡도가 O(N^2)이 된다.
[1, 2, 3, 4, 5]라는 리스트가 있을 때,
피벗을 1, 2, 3, 4, 5 순으로 돌아가면서 설정했다고 가정하면,
피벗이 1일 경우, n-1번 연산 수행
피벗이 2일 경우, n-1번 연산 수행
...
동일한 과정을 배열 내의 데이터 수만큼 진행하게 되고
매번 n-1개의 데이터를 비교하게 된다.
그러므로, 최악의 경우, O(n^2) 라는 시간 복잡도를 가지게 된다.
이런 문제점에도 불구하고 퀵소트가 여전히 빠른 알고리즘으로 인정받는 이유는 완전히 정렬된 배열에 대해 퀵정렬을 수행할 가능성이 매우 적기 때문이다.
이 최악의 경우를 피하기 위한, 피봇의 선정 방법은 아래 3가지가 있다.
- 첫번째 값이나 마지막 값을 피벗으로 선정한다.
- 첫번째 값, 가운데 값, 마지막 값 중에 중간값을 피벗으로 선정한다.(Median of Three)
- 무작위 값을 피벗으로 선정한다.
반면에 리스트가 대략적인 절반으로 계속 나뉘어진다면 리스트의 요소 갯수로 만들어지는 완전이진트리의 높이인 log n에 대해 비교연산이 n번 수행되므로 시간 복잡도는 𝛩(nlogn) 이 된다.
분할정복이란?
하나의 문제를 작은 문제로 나눈 후 각 문제에 대한 답을 재귀 호출을 이용하여 계산하고,
각 부분의 답으로부터 전체 문제의 답을 도출하는 방법이다.
대표적인 예시로는 이진 탐색(Binary Search), 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort) 등이 있다.