이번 글에서는 숫자로 이루어진 배열을 입력받아 퀵 정렬(Quick Sort) 알고리즘으로 오름차순 정렬하는 자바스크립트 함수를 직접 구현해 보겠습니다.
퀵 정렬(Quick Sort)이란?
퀵 정렬은 대표적인 분할 정복(Divide and Conquer) 방식의 정렬 알고리즘입니다. 매 단계마다 배열에서 피벗(pivot)이라 불리는 기준 요소를 하나 선택하고, 피벗보다 작은 값은 모두 왼쪽으로, 큰 값은 모두 오른쪽으로 이동시킵니다(내림차순 정렬 시에는 반대). 이후 분할된 각 영역에 대해 같은 과정을 재귀적으로 반복하면 전체 배열이 정렬됩니다.
퀵 정렬의 평균 시간 복잡도는 O(n log n)으로 매우 효율적이며, 실무에서 가장 널리 쓰이는 정렬 알고리즘 중 하나입니다.
동작 원리
- 배열의 가운데 요소를 피벗으로 선택합니다.
- 왼쪽 포인터는 피벗보다 크거나 같은 값을 만날 때까지 오른쪽으로 이동합니다.
- 오른쪽 포인터는 피벗보다 작거나 같은 값을 만날 때까지 왼쪽으로 이동합니다.
- 두 포인터가 서로 지나치지 않았다면 두 값을 교환(swap)하고 포인터를 한 칸씩 이동합니다.
- 포인터가 교차하면 현재 위치를 기준으로 배열을 나누고, 좌우 영역에 대해 재귀적으로 정렬을 수행합니다.
예제 코드
구현 코드는 다음과 같습니다.
const arr = [43, 3, 34, 34, 23, 232, 3434, 4, 23, 2, 54, 6, 54];
// 배열에서 "피벗" 요소를 찾아 다른 모든 요소와 비교한 뒤,
// 값의 크기에 따라 피벗 앞 또는 뒤로 요소들을 이동시킵니다.
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 함수가 전체 정렬 흐름을 담당하고, partition 함수가 피벗을 기준으로 배열을 분할하는 역할을 담당합니다. 특히 ES6의 구조 분해 할당(destructuring)을 활용하면 별도의 임시 변수 없이 두 요소를 간결하게 교환할 수 있다는 점이 눈에 띕니다. 퀵 정렬은 최악의 경우 O(n²)까지 성능이 저하될 수 있지만, 가운데 요소를 피벗으로 선택하는 방식을 사용하면 대부분의 경우 안정적으로 빠른 정렬 성능을 기대할 수 있습니다.