Quick Sort (퀵 정렬)
하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.
퀵 정렬은 다음의 단계들로 이루어진다.
분할 (Divide)
•
입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할 한다.
정복 (Conquer)
•
부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면, 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.
결합 (Combine)
•
정렬된 부분 배열들을 하나의 배열에 합병한다.
→ 순환 호출이 한번 진행될 때마다 최소한 하나의 원소(피벗)는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.
퀵 정렬의 특징
•
퀵 정렬은 재귀적으로 정의되므로, 재귀 호출에 따른 스택이 사용된다.
•
이때 스택의 깊이는 n개의 원소에 대해 logn에 비례하므로, 공간복잡도는 O(nlogn)이다.
•
따라서 in-place 정렬이라고 하기 힘들지만, 실용적으로는 상대적으로 작은 메모리만을 사용하므로, 흔히 in-place 정렬이라고 기술하기도 한다.
•
퀵 정렬은 최악의 경우 pivot이 배열 내에서 가장 작은 값 또는 가장 큰 값으로 설정된다면, 원소 n개에 대해서 n번, (n-1)번, (n-2)번 … 1번의 비교가 필요하므로 시간복잡도가 O(n^2)가 된다.
•
하지만 평균 시간복잡도는 O(nlonn) 으로 매우 빠르다. pivot 값이 적절히 설정된다면, 그 속도가 매우 빠르다. 따라서 pivot값을 잘 설정하는 것이 중요하다.
•
퀵 정렬은 중복된 키 값이 순서대로 바뀌지 않을 수 있어 not-stable하다.
퀵 정렬의 장단점
장점
•
속도가 빠르다.
•
시간복잡도가 O(nlogn)를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
•
추가 메모리 공간을 필요로 하지 않는다.
•
퀵 정렬은 O(logn) 만큼의 메모리를 필요로 한다.
단점
•
정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.
•
퀵 정렬의 불균형 분할을 방지하기 위하여 피벗을 선택할 때, 더욱 리스트를 균등하게 분할할 수 있는 데이터를 선택한다.
•
ex) 리스트 내의 몇 개의 데이터 중에서 크기 순으로 중간값(medium)을 피벗으로 선택한다.