*분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법*비균등하게 분할한다.하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.
퀵 정렬은 재귀적으로 정의되므로 재귀 호출에 따른 스택이 사용된다. 이때 스택의 깊이는 n개의 원소에 대해 logn에 비례하므로 공간복잡도는 O(nlogn)이다. 따라서 in-place 정렬이라고 하기 힘들지만, 실용적으로는 상대적으로 작은 메모리만을 사용하므로 흔히 in-place 정렬이라고 기술하기도 한다.
퀵 정렬은 최약의 경우 pivot이 배열 내에서 가장 작은 값 또는 가장 큰 값으로 설정된다면 원소 n개에 대해서 n번, (n-1)번, (n-2)번 … 1번의 비교가 필요하므로 시간복잡도가 최대 O(n^2) 이 된다.
하지만 평균 시간 복잡도는 O(nlogn) 으로 매우 빠르다. pivot 값이 적절히 설정된다면 그 속도는 매우 빠르다.
따라서 pivot값을 잘 설정하는 것이 중요하다.
퀵 정렬은 중복된 키 값이 순서대로 바뀌지 않을 수 있어 not-stable 하다.
(예를들어 [7, 7, 1]을 오름차순으로 퀵 정렬 수행)
// arr: [3, 6, 8, 10, 1, 2, 1]
function quickSort(arr) {
const len = arr.length;
if (len <= 1) return arr;
const pivot = arr[parseInt(len / 2)];
const left = arr.filter((x) => x < pivot);
const middle = arr.filter((x) => x === pivot);
const right = arr.filter((x) => x > pivot);
return [...quickSort(left), ...middle, ...quickSort(right)];
}
// result: [1, 1, 2, 3, 6, 8, 10]