퀵 정렬(Quick Sort)이란?
퀵 정렬(Quick Sort)은 JavaScript에서 가장 중요하고 널리 사용되는 정렬 알고리즘 중 하나입니다. 평균 시간 복잡도가 O(n log n)으로 매우 효율적이며, 분할 정복(Divide and Conquer) 전략에 기반해 동작합니다.
퀵 정렬은 배열에서 임의의 값인 피벗(pivot)을 하나 선택하는 것부터 시작합니다. 그런 다음 배열의 나머지 요소들을 피벗보다 작은 값과 큰 값, 두 그룹으로 나눕니다.
이후 피벗보다 작은 그룹과 큰 그룹 각각에 대해 동일한 절차를 반복 적용합니다. 즉, 각 그룹마다 새로운 피벗을 선택하고 다시 두 개의 하위 그룹으로 분할하는 과정을 거치는 것입니다.
이러한 분할 작업을 반복하다 보면 결국 하위 그룹에는 요소가 하나만 남거나 아예 비어 있어 더 이상 비교할 요소가 없는 상태가 됩니다. 지금까지 피벗으로 선택된 값들은 이미 제자리에 배치된 상태이므로, 모든 결과를 합치면 정렬이 완료됩니다.
구현 예제
<html>
<body>
<script>
function quickSort(originalArr) {
if (originalArr.length <= 1) {
return originalArr;
} else {
var leftArr = [];
var rightArr = [];
var newArr = [];
var pivot = originalArr.pop(); // 피벗 값 선택
var length = originalArr.length;
for (var i = 0; i < length; i++) {
if (originalArr[i] <= pivot) { // 피벗 값과 비교
leftArr.push(originalArr[i]);
} else {
rightArr.push(originalArr[i]);
}
}
// 정렬이 완료될 때까지 재귀적으로 호출
return newArr.concat(quickSort(leftArr), pivot, quickSort(rightArr));
}
}
var myArray = [9, 0, 2, 7, -2, 6, 1];
document.write("원본 배열: " + myArray);
var sortedArray = quickSort(myArray);
document.write("정렬된 배열: " + sortedArray);
</script>
</body>
</html>실행 결과
원본 배열: 9,0,2,7,-2,6,1 정렬된 배열: -2,0,1,2,6,7,9
참고 사항
위 예제에서 사용한 document.write()는 현재 웹 표준에서 권장되지 않는 방식입니다. 최신 개발 환경에서는 다음과 같이 console.log()를 사용하는 것이 좋습니다.
const myArray = [9, 0, 2, 7, -2, 6, 1];
console.log("원본 배열:", myArray);
console.log("정렬된 배열:", quickSort(myArray));또한 위 구현은 이해하기 쉽도록 작성된 버전으로, 배열을 직접 수정하지 않고 새로운 배열을 생성하는 방식입니다. 실무에서는 메모리 효율을 위해 제자리(in-place) 방식으로 구현하기도 하며, 이미 정렬된 배열이 입력될 경우 최악의 시간 복잡도 O(n²)가 될 수 있으므로 피벗을 무작위로 선택하는 방식을 함께 고려하는 것이 좋습니다.