이전에 버블, 삽입, 선택 정렬에 대해 공부했을때 이 세가지 정렬 알고리즘은 작은데이터를 정렬할때 맞는 알고리즘이였습니다. 그렇다면 큰 데이터에 맞는 퀵정렬과 병합정렬에 대한 내용을 공유해보고자 합니다.
퀵정렬
퀵정렬은 큰데이터를 효과적으로 정렬할 수 있는 알고리즘 중 하나입니다. 퀵정렬은 다른원소와 비교를 통해서 정렬하는 "비교 정렬"에 속한다고 합니다. 또한 분할 정복 방법을 통해서 리스트를 정렬합니다. 분할 정복 방법을 사용하는것의 이점은 하나의 큰 문제를 작은 문제로 쪼게 병렬적으로 해결할 수 있기 때문에 여러 정렬 알고리즘 중 시간적 효율이 좋은 정렬 방법이라고 할 수 있습니다.
퀵정렬에 대한 설명중 다음과 같은 설명이 있습니다.
퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고(그 이유는 메모리 참조가 지역화되어 있기 때문에 CPU 캐시의 히트율이 높아지기 때문이다.), 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다.
퀵 정렬은 메모리 접근 패턴이 지역적(locality)인 특성을 가지고 있습니다. 이는 데이터가 메모리에서 연속적으로 저장되고 접근되기 때문에, CPU가 데이터를 처리할 때 캐시를 효과적으로 활용할 수 있다는 뜻입니다. CPU는 한 번 로드한 메모리 데이터를 캐시에 저장하므로, 가까운 시점에 다시 사용할 때 빠르게 접근할 수 있습니다.
여기서 지역적 이라는 말의 의미는 데이터 접근이 특정 메모리 영역에 집중되는 패턴으로 퀵 정렬이 재귀적으로 배열을 분할하면서 작은 범위에서 작업하기 때문에 발생합니다.
또한, 위 설명을 좀 더 이해하기 위해 퀵정렬의 시간복잡도를 미리 살펴보겠습니다. 퀵 정렬의 최악 시간 복잡도는 O(n2)입니다. 하지만, 이 상황이 발생할 확률은 매우 낮습니다. 이미 정렬된 데이터에서 항상 최악의 피벗을 선택(예: 배열의 첫 번째나 마지막 요소)하면 O(n2) 시간이 걸립니다.
실질적인 구현에서는 "랜덤 피벗 선택", "중간값 피벗", "Median-of-three(첫 번째 요소, 중간 요소, 마지막 요소 세 가지 값중 중간값을 선택하는 것)"과 같은 전략을 사용해 이런 상황을 회피합니다. (이런 피벗 선택방법을 선택하면 되기 떄문에 최악의 시간 복잡도가 발생할 확률이 낮습니다.) 결과적으로, 대부분의 경우 퀵 정렬의 시간 복잡도는 O(nlogn)에 가깝게 됩니다.
그러면, 이런 퀵정렬은 어떻게 구현할 수 있을까요? 다음과 같은 순서를 따르면 됩니다.
- 종료 조건 : 배열의 길이가 1이하라면, 함수를 종료합니다.
- 피벗을 선택합니다.
- 피벗을 기준으로 작은값은 left배열에 높은 값은 right배열에 넣습니다.
- left와 right배열을 재귀적으로 정렬합니다.
- [left배열, 피벗, right 배열] 배열을 합쳐 반환합니다.
위와 같이 작성한 JavaScript코드는 다음과 같습니다. Median-of-three 으로 구현해보았습니다.
function quickSort(list) {
if (list.length <= 1) {
return list;
}
// Median-of-three 방식으로 피벗 선택
const first = list[0]; // 첫 번째 요소
const midIndex = Math.floor(list.length / 2); // 중간 요소의 인덱스
const middle = list[midIndex]; // 중간 요소
const last = list[list.length - 1]; // 마지막 요소
// 첫 번째, 중간, 마지막 요소 중 중간값 선택
const pivot = [first, middle, last].sort((a, b) => a - b)[1];
const pivotIndex = list.indexOf(pivot);
// 배열 분할 초기화
const left = [];
const right = [];
// 배열 순회하면서 분할
for (let i = 0; i < list.length; i++) {
if (i === pivotIndex) continue; // 피벗 요소는 건너뜀
if (list[i] < pivot) {
left.push(list[i]);
} else {
right.push(list[i]);
}
}
// 재귀적으로 정렬 후 병합
return [...quickSort(left), pivot, ...quickSort(right)];
}퀵 정렬의 시간복잡도는 입력 데이터의 분포에 따라 달라집니다. 퀵 정렬의 시간복잡도는 다음과 같습니다.
1. 최선의 경우 (Best Case): O(n log n)
매번 피벗이 배열을 완벽하게 균등하게 나눌 때 발생합니다. 즉, 피벗이 항상 배열의 중앙값에 가까운 경우입니다.
- 배열이 n개의 요소로 시작한다고 가정합니다.
- 각 단계에서 배열을 절반씩 나누며, 분할 작업에 O(n)이라는 시간복잡도가 소요됩니다.
- 분할 작업: 배열 전체를 순회하며 피벗보다 작은 값과 큰 값을 나누는 데 O(n) 시간이 걸립니다.
- 배열이 절반씩 나뉘므로, 총 분할 단계 수는 log n에 비례합니다.
결과적으로, ( O(n)) 분할 작업이( log n) 단계 동안 반복되므로 총 시간복잡도는 O(nlog n) 입니다.
2. 최악의 경우 (Worst Case): O(n2)
- 피벗이 매번 배열의 가장 큰 값 또는 가장 작은 값을 선택할 때 발생합니다.
- 피벗 선택이 배열을 크게 나누지 못하고, 한쪽에만 데이터를 몰아넣게 됩니다.
- 분할 단계에서 첫 번째는 ( n ), 두 번째는 ( n-1 ), 세 번째는 ( n-2 )개 요소를 처리하므로 O(n2)이 됩니다.
3. 평균적인 경우 (Average Case): ( O(n \log n) )
피벗이 배열을 적절히 균등하게 분할하는 경우.
- 평균적으로 각 분할 단계에서 배열이 약 절반씩 나뉜다고 가정합니다.
- 따라서 분할 단계 수는 log n, 각 단계의 분할 작업은 O(n)이므로 평균 시간복잡도는 O(nlog n)이 됩니다.
퀵 정렬이 실질적으로 빠른 이유는 다음과 같습니다.
- 시간복잡도 O(nlog n)를 평균적으로 유지하여 효율적입니다.
- 데이터 접근 패턴이 지역적(locality)을 띠어 캐시 효율이 높습니다.
- 제자리 정렬로 추가 메모리가 거의 필요하지 않으므로 공간 효율적입니다.
병합 정렬
병합정렬 또한 퀵정렬과 마찬가지로 비교 정렬에 속합니다. 또한, 분할 정복알고리즘으로 정렬을 구현하는것또한 동일합니다. 퀵정렬과 다른 점은 병합 정렬은 안정정렬에 속한다는 것입니다. 보통 n-way 합병 정렬이라고 합니다. n-way는 하나의 리스트를 몇개만큼 분할할지에 대한 방법으로 일반적으로 2-way 병합정렬을 사용한다고 합니다.
병합 정렬은 다음과 같이 설명할 수 있습니다.
- 리스트의 길이가 1 이하이면 이미 정렬된 것으로 간주합니다.
- 그렇지 않으면, 비슷한 크기의 두개의 리스트로 나눕니다.
- 각 부분을 재귀적으로 정렬합니다.
- 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병합니다.
- 이 과정을 반복합니다.
위 과정을 자바스크립트 코드로 옮긴건 다음과 같습니다.
function mergeSort(list) {
if (list.length <= 1) {
return list;
}
// 반으로 나눈다.
const mid = Math.floor(list.length / 2);
const left = mergeSort(list.slice(0, mid));
const right = mergeSort(list.slice(mid));
return merge(left, right);
}
function merge(left, right) {
const result = [];
let i = 0,
j = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result.push(left[i]);
i++;
} else {
result.push(right[j]);
j++;
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}병합 정렬(Merge Sort)의 시간복잡도는 입력 데이터의 분포와 관계없이 항상 O(nlog n)입니다. 병합 정렬의 시간복잡도를 다시한번 단계별로 설명해 보면 다음과 같습니다.
병합 정렬은 분할 정복(Divide and Conquer) 알고리즘으로 작동합니다.
1. 분할(Divide) : 배열을 한 요소로 나뉠 때까지 절반씩 나눠 재귀적으로 분할합니다.
2. 정복(Conquer) : 분할된 배열들을 두 개씩 정렬하며 병합합니다.
3. 병합(Merge) : 병합 단계에서는 두 정렬된 배열을 하나로 합치며 정렬합니다.
시간복잡도
(1) 분할 단계 시간복잡도
- 배열을 계속 절반으로 나누므로, 분할 작업의 단계 수는 log n 입니다.
- 분할 자체는 배열을 나누기만 하기 때문에 O(1) 시간에 이루어집니다.
(2) 병합 단계의 시간복잡도
- 각 병합 단계에서 두 배열을 합치는 데 O(n) 시간이 소요됩니다.
- 병합 과정에서는 두 배열을 순회하며 원소를 비교하고, 결과 배열에 정렬된 값을 추가합니다.
- 배열이 log n 단계로 나뉘었으므로, 병합 작업은 각 단계에서 O(n) 시간씩 log n 단계 동안 반복됩니다.
(3) 전체 시간복잡도
- 각 병합 단계에서 O(n) 작업이 필요하고, 이런 작업이 log n 단계 동안 반복합니다.
- 따라서 병합 정렬의 총 시간복잡도는: O(nlog n) 입니다.
병합 정렬은 왜 항상 O(n \log n)일까?
- 배열을 항상 절반으로 나누기 때문에, 최악의 경우에도 균등하게 분할됩니다.
- 또한, 병합 정렬은 이미 정렬된 데이터에서도 동일한 절차를 따르므로 항상 O(nlog n)을 유지합니다.
자바스크립트의 sort함수는 어떤 정렬을 사용할까?
이전에 자바스크립트의 sort 함수에 대해 간략히 설명한 적이 있습니다. 정렬 알고리즘을 공부하다 보니, 자바스크립트에서 제공하는 내장 함수인 sort 함수가 정확히 어떤 알고리즘을 사용하는지 궁금해졌습니다.
자바스크립트의 sort 함수는 사용 중인 엔진에 따라 구현 방식이 조금씩 다를 수 있습니다. 하지만 대부분의 경우 비슷한 방식으로 구현되어 있습니다. 예를 들어, 우리가 많이 사용하는 V8 엔진(Chrome과 Node.js)에서는 sort 함수가 TimSort 알고리즘을 사용합니다.
관련해서 모던 자바스크립트 Deep Dive 책에서 Array.prototype.sort에 대해 언급한 내용을 찾아보니 다음과 같은 내용이 있었습니다. 과거에는 자바스크립트의 sort 메서드가 퀵 정렬(Quick Sort) 알고리즘을 사용했는데, 이 알고리즘은 동일한 값의 요소가 중복될 때 초기 순서를 유지하지 못하는 단점이 있었습니다. 이는 불안정한 정렬 알고리즘의 특징이기도 합니다. 이러한 문제를 해결하기 위해 ECMAScript 2019부터는 TimSort 알고리즘이 사용되도록 변경되었습니다.
TimSort란?
TimSort는 합병 정렬(Merge Sort)과 삽입 정렬(Insertion Sort)을 결합한 정렬 알고리즘입니다. 이 알고리즘은 다음과 같은 장점을 가지고 있습니다:
- 동일한 값의 요소가 있을 경우, 초기 순서를 유지합니다.
- 데이터가 이미 부분적으로 정렬된 경우(예: 대부분 정렬된 데이터), 매우 빠르게 동작하도록 설계되었습니다.
결론적으로, 자바스크립트의 sort 함수는 과거에는 퀵 정렬을 기반으로 작동했지만, ECMAScript 2019 이후부터는 안정성과 효율성을 고려해 TimSort 알고리즘으로 전환되었습니다. 이를 통해 동일한 값의 요소 순서를 유지하며, 대부분의 실제 데이터에서 더 빠르게 정렬을 수행할 수 있습니다.
결론
실제로 아무 생각 없이 sort 함수를 사용해 왔지만, 이번에 합병 정렬(Merge Sort)과 퀵 정렬(Quick Sort)을 공부하면서 자바스크립트의 sort 함수가 어떤 정렬 알고리즘을 사용하는지 이해하게 되었습니다.
프론트엔드 개발을 하다 보면 종종 클라이언트 쪽에서 정렬 작업을 처리해야 할 때가 있는데, 특히 대규모 데이터를 정렬해야 할 때 성능을 고려한 최적화가 중요하다는 걸 다시금 느꼈습니다. 이번 공부를 통해, 만약 이 내용을 미리 알았다면 당시 개발에서 더 나은 성능 최적화를 고민하며 구현할 수 있지 않았을까 하는 아쉬움도 들었습니다.
정렬 알고리즘에 대해 이해하고 sort 함수의 작동 방식을 알게 된 만큼, 앞으로는 성능과 효율성을 더 신경 쓰며 정렬 작업을 처리할 수 있을 것 같습니다.
