퀵 정렬은 하나의 중심(pivot) 값을 기준으로 큰 값과 작은 값을 분류하고 이 작업을 반복하여 정렬하는 방법임.
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]);
}
}
return [...quickSort(left), pivot, ...quickSort(right)];
};
console.log(quickSort([6, 3, 5, 1, 9, 4, 8, 2, 7]));- 첫 요소인 6을 기준으로 잡아서 이보다 작은 수를 left, 큰 수를 right로 분류하고 이 작업을 세분화해서 반복 진행하면 최종적으로 정렬된 배열을 반환할 수 있다.
- 퀵 정렬은 최악의 경우를 제외하면 O(NlogN)의 시간 복잡도를 갖는 속도가 장점이지만 단점은 최악의 경우(이미 정렬된 배열) 시간 복잡도가 O(N^2)로 대폭 증가하고 불안정 정렬(unstable sort, 동일한 값에 대해서는 순서가 바뀔 수 있음)이라는 점이다.
- 최악의 경우는 기준(pivot)으로 뽑은 수가 항상 제일 큰 수이거나 제일 작은 수일 경우이다. 이럴 경우는 나중에 두 배열로 나누더라도 한 배열은 비어있고, 한 배열은 꽉 차있다.