숫자 배열을 입력받아 퀵 정렬(Quick Sort) 알고리즘으로 정렬하는 JavaScript 함수를 작성해 보겠습니다.
퀵 정렬(QuickSort)이란?
퀵 정렬은 대표적인 분할 정복(Divide and Conquer) 방식의 정렬 알고리즘입니다. 각 순회 단계마다 배열에서 기준이 되는 피벗(pivot) 요소를 하나 선택하고, 피벗보다 작은 요소는 모두 왼쪽으로, 큰 요소는 모두 오른쪽으로 배치합니다(오름차순 정렬 기준이며, 내림차순일 경우 그 반대로 동작합니다).
이렇게 피벗을 기준으로 나뉜 좌우 두 구간에 같은 과정을 재귀적으로 반복하면 전체 배열이 정렬됩니다. 퀵 정렬의 평균 시간 복잡도는 O(n log n)으로 매우 빠르기 때문에 실무에서도 가장 널리 사용되는 정렬 알고리즘 중 하나입니다.
예제 코드
그럼 이제 해당 함수의 전체 코드를 살펴보겠습니다.
const arr = [43, 3, 34, 34, 23, 232, 3434, 4, 23, 2, 54, 6, 54];
// 배열에서 피벗(pivot)이 될 요소를 하나 골라 다른 모든 요소와 비교한 뒤,
// 값의 크기에 따라 피벗 앞 또는 뒤로 요소들을 이동시킵니다.
const quickSort = (arr, left = 0, right = arr.length - 1) => {
let len = arr.length, index;
if(len > 1) {
index = partition(arr, left, right)
if(left < index - 1) {
quickSort(arr, left, index - 1)
}
if(index < right) {
quickSort(arr, index, right)
}
}
return arr
}
const partition = (arr, left, right) => {
let middle = Math.floor((right + left) / 2),
pivot = arr[middle],
i = left, // 포인터를 배열의 첫 번째 항목에서 시작
j = right // 포인터를 배열의 마지막 항목에서 시작
while(i <= j) {
// 왼쪽 포인터가 가리키는 값이 피벗보다 클 때까지 오른쪽으로 이동
while(arr[i] < pivot) {
i++
}
// 오른쪽 포인터가 가리키는 값이 피벗보다 작을 때까지 왼쪽으로 이동
while(arr[j] > pivot) {
j--
}
// 왼쪽 포인터가 오른쪽 포인터보다 작거나 같으면 두 값을 교환
if(i <= j) {
[arr[i], arr[j]] = [arr[j], arr[i]] // ES6 구조 분해 할당을 활용한 스왑
i++
j--
}
}
return i
}
console.log(quickSort(arr));
실행 결과
위 코드를 실행하면 콘솔에 다음과 같이 정렬된 배열이 출력됩니다.
[
2, 3, 4, 6, 23,
23, 34, 34, 43, 54,
54, 232, 3434
]
코드 동작 원리 요약
- quickSort 함수: 배열의 길이가 1보다 큰 경우 partition 함수를 호출해 피벗의 최종 위치(index)를 구한 뒤, 피벗을 경계로 좌측 구간과 우측 구간을 각각 재귀적으로 정렬합니다.
- partition 함수: 배열의 중앙값을 피벗으로 삼고, 왼쪽 포인터(i)와 오른쪽 포인터(j)를 이동시켜 조건에 맞지 않는 두 값을 서로 교환(swap)합니다. ES6의 구조 분해 할당 문법을 사용하면 임시 변수 없이 간결하게 값을 맞바꿀 수 있습니다.
- 재귀 종료 조건: 더 이상 나눌 구간이 없으면(left >= index - 1 또는 index >= right) 재귀 호출이 멈추고 정렬이 완료됩니다.