이전 글에서는 버블,선택,삽입 정렬에 대해 살펴보았다.
이 정렬들은 공통적으로 O(n²)의 시간복잡도를 가진다.
따라서 구현하기는 수월하지만 정렬할 데이터들이 많아지면 비효율적으로 동작하기 때문에 실제로는 더 효율적인 알고리즘을 사용한다.
대표적인 알고리즘이 바로
- 합병 정렬
- 퀵 정렬
- 지수 정렬
이다.
합병 정렬
합병 정렬은 분할과 정복 전략을 사용하는 정렬 알고리즘이다.
말그대로 배열을 더 작은 배열로 나누고, 그걸 더 작은 하위 배열로 나눈다.
동작하는 방식은
- 배열을 더 작은 배열로 분할한다.
- 더 이상 나눌 수 없을 때까지 분할한다.
- 다시 합치면서 배열을 정렬한다.
예를 들어,
8개 배열이 있다.
[8,3,5,4,7,6,1,2]먼저 배열을 계속 나눈다.
[8,3,5,4] [7,6,1,2]
[8,3] [5,4] [7,6] [1,2]
[8] [3] [5] [4] [7] [6] [1] [2]각 배열이 한 개의 요소만 가지게 되면 다시 합치기 시작한다.
하나의 배열,하나의 배열을 합칠 때 두 개를 정렬하면서 합치는 것이다.
합병 정렬의 핵심은 두개의 정렬된 배열을 합치는 과정이다.
예를 들어 다음과 같은 두 배열이 있다고 가정해보자.
[3,8]
[4,5]
각 배열은 이미 정렬되어 있다.
이때 두 개의 포인터 i,j를 사용한다.
- arr1[i]와 arr2[j]를 비교한다.
- 더 작은 값을 새로운 배열에 넣는다.
- 해당 포인터를 한 칸 이동한다.
- 배열의 끝에 도달할 때까지 반복한다.
function merge(arr1, arr2){
let results = [];
let i = 0;
let j = 0;
while(i < arr1.length && j < arr2.length){
if(arr2[j] > arr1[i]){
results.push(arr1[i]);
i++;
} else {
results.push(arr2[j]);
j++;
}
}
while(i < arr1.length){
results.push(arr1[i]);
i++;
}
while(j < arr2.length){
results.push(arr2[j]);
j++;
}
return results;
}합병 정렬은 보통 재귀를 사용해 구현한다.
배열을 계속 반으로 나누다가 길이가 1이 되면 다시 합친다.
function mergeSort(arr){
if(arr.length <= 1) return arr;
let mid = Math.floor(arr.length/2);
let left = mergeSort(arr.slice(0,mid));
let right = mergeSort(arr.slice(mid));
return merge(left,right);
}Merge Sort 시간복잡도
합병 정렬의 시간복잡도는 다음과 같다.
O(n log n)- 배열을 반씩 나누는 과정 → log n
- 각 단계에서 전체 배열을 합치는 과정 → n
따라서
n × log n이 된다.
퀵 정렬
퀵 정렬 역시 분할 정복 알고리즘이다.
하지만 합병 정렬과 달리 배열을 나눈 뒤 다시 합치는 과정이 없다.
대신 하나의 기준값을 정하고 데이터를 분할한다.
이 기준값을 Pivot(피벗)이라고 한다.
Quick Sort 동작 방식
- 배열에서 Pivot을 선택한다
- Pivot보다 작은 값은 왼쪽
- Pivot보다 큰 값은 오른쪽
- Pivot이 올바른 위치에 배치된다
- 왼쪽과 오른쪽 배열을 재귀적으로 다시 정렬
예를 들어 다음 배열이 있다고 가정해보자.
[4,8,2,1,5,7,6,3]Pivot을 첫 번째 요소인 4로 선택한다.
정렬 후
[2,1,3] 4 [8,5,7,6]이제 왼쪽과 오른쪽 배열에 대해 다시 퀵 정렬을 수행한다.
function pivot(arr, start=0, end=arr.length-1){
const swap = (arr,i,j)=>{
[arr[i],arr[j]] = [arr[j],arr[i]]
}
let pivot = arr[start];
let swapIdx = start;
for(let i = start+1; i <= end; i++){
if(arr[i] < pivot){
swapIdx++;
swap(arr,swapIdx,i);
}
}
swap(arr,start,swapIdx);
return swapIdx;
}재귀를 이용한 ver.
function quickSort(arr, left=0, right=arr.length-1){
if(left < right){
let pivotIndex = pivot(arr,left,right);
quickSort(arr,left,pivotIndex-1);
quickSort(arr,pivotIndex+1,right);
}
return arr;
}Quick Sort 시간복잡도
평균적인 경우
O(n log n)하지만 최악의 경우는 다음과 같다.
O(n²)예를 들어
- 이미 정렬된 배열
- Pivot이 항상 최소값 또는 최대값인 경우
이 경우 분할이 제대로 이루어지지 않기 때문이다.
기수 정렬
앞서 살펴본 정렬 알고리즘들은 모두 비교 기반 정렬 알고리즘이다.
즉, 두 값을 비교하면서 정렬을 수행한다.
이러한 비교 기반 정렬 알고리즘의 이론적 최적 시간복잡도는 O(n log n)이다.
하지만 기수 정렬은 비교를 사용하지 않는 정렬 알고리즘이다.
대신 숫자의 자릿수(digit)를 이용해 정렬을 수행한다.
Radix Sort 동작 원리
기수 정렬은 숫자의 각 자리수를 기준으로 정렬한다.
예를 들어 다음 배열이 있다고 가정해보자.
[23,345,5467,12,2345,9852]먼저 1의 자리 기준으로 정렬한다.
그 다음
- 10의 자리
- 100의 자리
순서로 계속 정렬을 진행한다.
이 과정을 반복하면 전체 배열이 정렬된다.
자릿수 추출 함수
특정 자리의 숫자를 구하기 위해 다음 함수를 사용할 수 있다.
function getDigit(num, i){
return Math.floor(Math.abs(num) / Math.pow(10,i)) % 10;
}여기서
Math.pow(a,b)는 a의 b제곱을 의미한다.
버킷 배열 생성
각 자릿수(0~9)를 위한 10개의 배열을 생성한다.
Array.from({length:10}, ()=>[])배열 합치기
버킷 배열을 하나로 합칠 때는 다음과 같이 사용할 수 있다.
[].concat(...digitBuckets)[[1],[2],[3]] 을 [1,2,3]
으로 합칠 수 있다.
function radixSort(nums){
let maxDigitCount = mostDigits(nums);
for(let k = 0; k < maxDigitCount; k++){
let digitBuckets = Array.from({length:10}, ()=>[]);
for(let i = 0; i < nums.length; i++){
let digit = getDigit(nums[i],k);
digitBuckets[digit].push(nums[i]);
}
nums = [].concat(...digitBuckets);
}
return nums;
}Radix Sort 시간복잡도
기수 정렬의 시간복잡도는 다음과 같다.
O(nk)여기서
- n → 배열의 길이
- k → 숫자의 자릿수
일반적으로 k는 작은 값이기 때문에 거의 O(n)에 가까운 성능을 가진다.
