퀵 정렬 (Quick Sort)
하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 정렬하는 분할 정복 알고리즘입니다. 실무에서 가장 널리 쓰이는 매우 빠른 정렬 알고리즘입니다.
평균 시간 복잡도는 O(n log n)이며, 최악의 경우(이미 정렬된 경우) O(n²)이 될 수 있습니다.
function quickSort(arr) {
if (arr.length <= 1) return arr;
const pivot = arr[arr.length - 1]; // 마지막 원소를 피벗으로 선택
const left = [];
const right = [];
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...quickSort(left), pivot, ...quickSort(right)];
}
const arr = [5, 3, 8, 4, 9, 1, 6];
console.log("초기 배열:", arr);
console.log("정렬 결과:", quickSort(arr));