알고리즘은 프로그래머스나 백준에서 푸는 문제가 아니라 연산(컴퓨팅) 시 입력된 자료를 원하는 출력의 형태로 만들어내는 처리 과정이다. 이 처리 과정이 얼마나 정확하고 효율적인지에 따라 좋고 나쁨을 판별할 수 있다.
여기서 많이 들어봤던 시간 복잡도의 개념이 나오는데, 다양한 정렬 알고리즘을 정리하고 비교해볼 때 참고해볼 예정이다.
⌛️ 시간 복잡도란?
입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구현했는지 확인하는 척도이다.
최악, 최선, 평균으로 나타낼 수 있는데 프로그래밍에서는 주로 최악의 상황을 염두하는 것이 중요하므로, Big-O 표기법을 사용한다. 자세한 정리는 여기를 참고하자!
A. 선형 탐색 (Linear Search Algorithm)
냅다 처음부터 끝까지 하나씩 둘러보는, 정확하지만 아주 효율적이지 못한 알고리즘이다.
자료가 정렬되지 않거나 정보가 아무것도 없어 하나씩 찾아야 하는 경우에는 유용하다.
왜 정렬해야하는가?
강의에서 한 학생이 (마지막에 놓인) 7을 찾기 위해 첫 번째 칸부터 끝까지 확인한 것처럼 선형 탐색은 평균적으로 최악의 상황에서 종료된다.
정렬하는 과정도 시간과 공간의 비용을 차지하긴 하지만, 매우 큰 자료인 경우 탐색 전에 먼저 정렬한다면 훨씬 효율적으로 찾을 수 있다.
B. 정렬
1. 버블 정렬 (Bubble Sort)
두 개의 인접한 자료를 비교하면서 차례차례 위치를 교환하는 방식으로 정렬한다. 결국 첫 번째 순환에서 가장 큰 수가 정렬되고, 두 번째에서는 그다음으로 큰 수가 정렬되며 이 모습이 물방울이 올라가는 것 같아 이름 붙여졌다.
단순한 로직이라 구현이 간편하고, 낱개로 하나하나 비교하기 때문에 정확하게 비교가 가능하지만 비교 횟수가 많아져 성능이 좋은 알고리즘은 아니다.
const bubbleSort = function (arr) {
for(let i = 0; i < arr.length; i++) {
let swapped;
// 순회하며 i번째와 i+1번째를 비교해 대-소 순서로 되어있으면 자리를 바꿔준다
for(let j = 0; j < arr.length; j++) {
if(arr[j] > arr[j+1]) {
[arr[j], arr[j+1]] = [arr[j+1], arr[j]];
swapped ++ ;
}
}
if(!swapped) break;
}
return arr;
};
2. 선택 정렬 (Selection Sort)
버블 정렬이 하나 하나 교환하는 방법이었다면, 선택 정렬은 반복해서 최솟값(또는 최댓값)을 찾아 비교하고 자리를 교환하는 방법이다.
버블 정렬과 마찬가지로 구현이 쉽다. 또한 교환 횟수가 적다는 장점은 있지만 자료의 상태와 무관하게 데이터를 비교하는데 O(n²)의 시간 복잡도를 가진다. 또한 동일한 값을 가지는 자료가 있다면 입력 순서가 보장되지 않는 불안정 정렬이다.
const selectionSort = function (arr) {
for (let i = 0; i < arr.length - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// i번째 인덱스 이후 더 작은 수가 없다면 자기 자신이 현재 최소값이므로 교환하지 않는다.
if (i !== minIndex) {
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
}
}
3. 삽입 정렬 (Insertion Sort)
버블, 선택 정렬과 다르게 데이터를 비교-교환하지 않는다. 자료를 정렬된 부분과 정렬되지 않은 부분으로 나누어 정렬되지 않은 부분의 자료가 정렬된 부분의 적당한 자리로 삽입되는 방식이다.
자료의 양이 적거나 대부분이 이미 정렬되어있는 경우 매우 효율적이다. 반대로 배열의 길이가 길어짐에 따라 효율성이 낮아진다.
const insertionSort = function (arr) {
let sorted = [arr[0]];
for (let i = 1; i < arr.length; i++) {
// 정렬된 값 중 최대값보다 현재값이 크다면 그냥 뒤에 달아준다
if (arr[i] >= sorted[i - 1]) {
sorted.push(arr[i]);
}
// 그렇지 않다면 어디 넣어줄지 찾는다.
else {
for (let j = 0; j < i; j++) {
if (arr[i] <= sorted[j]) {
sorted.splice(j, 0, arr[i])
break;
}
}
}
}
return sorted;
};
4. 병합 정렬 (Merge Sort)
데이비드의 좍좍 찢는 전화번호부 예시(이진 탐색)처럼 자료의 길이가 1이 될 때까지 계속해서 반으로 나누다가 다시 합쳐가며 정렬하는 방식이다. 최악의 상황에도 O(nlogn)의 시간 복잡도를 가지며 효율이 좋지만, 입력값이 작으면 삽입 정렬과 크게 다르지 않으므로 방대한 자료 정렬에 적합하다. 정렬 과정에서 배열을 복제하므로 필요한 메모리가 늘어나 공간 복잡도가 커진다는 단점이 있다.
const merge = function (left, right) { // 두 배열을 합치면서 정렬해준다
const result = [];
while (left.length > 0 && right.length > 0) {
left[0] <= right[0] ? result.push(left.shift()) : result.push(right.shift());
}
return [...result, ...left, ...right];
}
const mergeSort = function (arr) { // 재귀하며 쪼갠다
if (arr.length === 1) return arr;
const left = arr.slice(0, Math.ceil(arr.length / 2));
const right = arr.slice(Math.ceil(arr.length / 2));
return merge(mergeSort(left), mergeSort(right));
}[2, 5, 3] 같은 경우 [2, 5] 사이에 3을 넣으려면 어쨌든 n² 시간 복잡도의 비교 순환을 가지는 게 아닌가 생각했는데, 위 merge 함수를 통해 이해할 수 있었다.
이미 정렬된 왼쪽, 오른쪽 덩어리의 최솟값끼리만 비교하며 result라는 배열에 차곡차곡 넣고, 마지막에 spread 문법으로 합쳐준다.
쓰여있기엔 result, left, right 세 개의 배열을 합치는 것 같지만, 왼쪽 오른쪽 덩어리 중 하나라도 빈 배열이 돼야 while문이 종료되기 때문에 한쪽 덩어리가 전체적으로 작은 수로 이루어졌다면 다른 한쪽 덩어리는 끝까지 볼 필요가 없어진다.
5. 힙 정렬 (Heap Sort)
자료를 최대 힙 트리나 최소 힙 트리로 구성해 정렬한다. 최댓값이나 최솟값을 구하거나 가장 큰 수 n개 또는 가장 작은 수 n개를 구할 때 유용하며, 아무튼 간 트리를 만들고 최대(최소) 값을 추출하는 방식이므로 시간 복잡도는 언제나 O(nlogn)이 된다. 따라서 많은 데이터를 모두 정렬해야 할 경우에는 적합하지 않으며, 데이터의 순서를 보장하지 않는 불안정 정렬이라는 단점이 있다.
최소 힙 트리로 구현한다면 다음과 같다.
1. 최소 힙 형태로 최솟값이 root인 완전 이진트리(마지막 노드를 제외하고 모든 노드가 채워진 상태)로 정렬한다.
2. 최솟값인 root 값을 result 배열에 넣어주고, 트리에서 삭제한다.
3. 남은 heap을 다시 최소 힙 형태로 정렬한다.
3. heap 길이가 0이 될 때까지 2-3 과정을 반복한다.
function swap(idx1, idx2, arr) {
[arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
}
// 이진 트리로 Min heap을 만들어준다
function insert(heap, item) {
heap.push(item);
if (heap.length > 1) {
let curIdx = heap.length - 1;
let pIdx = Math.floor((curIdx - 1) / 2);
while (pIdx >= 0 && heap[curIdx] < heap[pIdx]) {
swap(curIdx, pIdx, heap);
curIdx = pIdx;
pIdx = Math.floor((curIdx - 1) / 2);
}
}
return heap;
}
// 정렬한 값(root) 트리에서 제거
function removeRoot(heap) {
swap(0, heap.length - 1, heap);
heap.pop();
if (heap.length === 0) return [];
let curIdx;
let minIdx = 0;
while (curIdx !== minIdx) {
curIdx = minIdx;
let left = curIdx * 2 + 1;
let right = curIdx * 2 + 2;
if (left < heap.length && heap[left] < heap[minIdx]) {
minIdx = left;
}
if (right < heap.length && heap[right] < heap[minIdx]) {
minIdx = right;
}
swap(curIdx, minIdx, heap);
}
return heap;
}
const heapSort = function (arr) {
let minHeap = arr.reduce((heap, item) => insert(heap, item), []);
const sorted = [];
while (minHeap.length > 0) {
sorted.push(minHeap[0]);
minHeap = removeRoot(minHeap);
}
return sorted;
};
6. 퀵 정렬 (Quick Sort)
임의의 값 pivot(주로 배열의 첫 요소)을 기준으로, pivot보다 크면 우측 작으면 좌측에 정렬한다. 배열을 이분화하며 점점 작은 문제로 재귀적으로 반복해 정렬하는 방식으로 시간 복잡도 O(nlogn)을 가진다.
매 단계마다 최소 한 개(pivot)의 원소가 자기 자리를 찾기 때문에 같은 시간 복잡도의 알고리즘 중에서도 가장 빨라 빠른 정렬이라는 이름이 붙게 되었다고 한다. 평균적으로 재귀 호출을 위해 O(logn)의 메모리를 필요로 한다.
단점으로는 불안정 정렬이라는 점과, 정렬된 리스트에서는 불균형적으로 분할하기 때문에 오히려 수행 시간이 불필요하게 길어지게 된다는 점이다. 따라서 pivot을 데이터의 중간값으로 선택해야 더욱 효율적으로 정렬할 수 있다.
const quickSort = function (arr) {
if(arr.length <= 1) return arr;
const pivot = arr[0];
const left = [];
const right = [];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < pivot) left.push(arr[i]);
else right.push(arr[i]);
}
return quickSort(left).concat(pivot, quickSort(right))
};'Computer Science' 카테고리의 다른 글
| 컴파일이란 무엇이며, 자바스크립트는 인터프리터 언어인가? (0) | 2022.01.14 |
|---|
