1. 소개
퀵정렬이란 pivot(중심축)을 정하고, 중심축 보다 작은 값들은 왼쪽으로, 큰 값들은 오른쪽으로 보내는것이다.
pivot을 정해 왼쪽 오른쪽으로 나누고 다시금 왼쪽 오른쪽에 대해 재귀적으로 pivot을 정해 왼쪽 오른쪽을 나누고.. 이 과정을 반복하다보면 결국 정렬이 완성 된다.
2. 작동개념
- 분할: 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분배열로 분할한다.
- 정복: 부분배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용해 다시 분할 정복 방법을 적용한다.
- 결합: 정렬된 부분 배열들을 하나의 배열에 합병한다.
- 순환 호출이 한번 진행될 때마다 최소한 하나의 원소(피벗)는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는것을 보장할 수 있다.
3. 시간복잡도
평균적으로 O(n log2 n) 실행시간을 가지는 매우 빠른 정렬 방법 중 하나이다.
그러나 이미 정렬된 배열을 첫번째 원소를 기준으로 퀵 정렬하는 경우는 최악의 시나리오 이며, O(n^2) 실행시간을 가진다.
4. 구현
const quickSort = function (arr) {
if (arr.length <= 1) return arr;
const pivot = arr[0];
const left = [];
const right = [];
for (let i = 1; i < arr.length; i++) {
if (arr[i] <= pivot) left.push(arr[i]);
else right.push(arr[i]);
}
const lSorted = quickSort(left);
const rSorted = quickSort(right);
return [...lSorted, pivot, ...rSorted];
};
5. 퀵 정렬과 병합 정렬
공통점
- 분할정복 알고리즘에 속한다.
- 평균적으로 O(n log n)의 성능을 갖는다.
- 둘 다 점점 탐색할 배열의 크기를 쪼개어 재귀함수에 넘겨준다.
차이점
- 병합정렬은 배열을 분할하는 방식이 반으로 쪼개는것
- 퀵 정렬은 크게 두가지의 분할방법이 있다.(1. 배열의 마지막값을 pivot으로 2. 배열의 중간값을 pivot으로)
- 퀵정렬은 병합정렬과 달리 메모리 공간을 사용하지 않는다.
(오직 재귀 콜 스택을 위한 메모리만 사용됨, 그에 비해 병합정렬은 매 번 새로운 배열을 만들어 내므로 메모리 사용량이 더 큼) - 병합정렬은 stable하지만, 퀵 정렬은 unstable 하다.