이번 글에서는 숫자 배열을 입력받아 퀵 정렬(QuickSort) 알고리즘을 적용해 오름차순 또는 내림차순으로 정렬하는 자바스크립트 함수를 작성해 보겠습니다.
퀵 정렬(QuickSort) 알고리즘이란?
퀵 정렬은 분할 정복(Divide and Conquer) 방식에 기반한 대표적인 정렬 알고리즘으로, 다음 단계를 따릅니다.
1단계 − 배열에서 임의의 요소 하나를 피벗(pivot)으로 선택합니다. 일반적으로 첫 번째 또는 마지막 요소를 사용하지만, 어떤 요소든 피벗이 될 수 있습니다.
2단계 − 피벗을 기준으로 배열을 분할(partition)합니다. 피벗보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 이동시킵니다.
3단계 − 왼쪽 파티션에 대해 재귀적으로 퀵 정렬을 수행합니다.
4단계 − 오른쪽 파티션에 대해 재귀적으로 퀵 정렬을 수행합니다.
퀵 정렬의 평균 및 최선의 경우 시간 복잡도는 O(n log n)입니다. 반면 최악의 경우에는 O(n²)까지 성능이 저하될 수 있는데, 이는 피벗이 항상 최솟값이나 최댓값으로 선택되어 배열이 극단적으로 한쪽으로만 나뉠 때 발생합니다.
예제 코드
재귀 방식으로 구현한 퀵 정렬 코드는 다음과 같습니다.
const arr = [5,3,7,6,2,9];
const swap = (arr, leftIndex, rightIndex) => {
let temp = arr[leftIndex];
arr[leftIndex] = arr[rightIndex];
arr[rightIndex] = temp;
};
const partition = (arr, left, right) => {
let pivot = arr[Math.floor((right + left) / 2)];
let i = left;
let j = right;
while (i <= j) {
while (arr[i] < pivot) {
i++;
};
while (arr[j] > pivot) {
j--;
};
if (i <= j) {
swap(arr, i, j); // 두 요소 교환
i++;
j--;
};
};
return i;
}
const quickSort = (arr, left = 0, right = arr.length - 1) => {
let index;
if (arr.length > 1) {
index = partition(arr, left, right);
if (left < index - 1) {
quickSort(arr, left, index - 1);
};
if (index < right) {
quickSort(arr, index, right);
};
}
return arr;
}
let sortedArray = quickSort(arr);
console.log(sortedArray);실행 결과
위 코드를 실행하면 콘솔에 다음과 같이 정렬된 배열이 출력됩니다.
[ 2, 3, 5, 6, 7, 9 ]