🍦

[JS] Sorting Algorithms


Bubble Sort(거품 정렬)

거품 정렬은 인접한 원소끼리 비교하고, 원소가 잘못된 순서라면 자리를 교환해 정렬하는 알고리즘이다.

비교를 1회전 진행하면 순서가 가장 뒤인 원소가 맨 뒤로 이동하기 때문에 다음 회전부터는 뒤로 이동시킨 원소를 제외시킨다. 회전마다 비교하는 원소가 하나씩 줄어들고, 비교할 원소가 없을 때까지 진행하면 정렬이 완료된다.

구현

1function bubbleSort(arr) { // ascending order
2 for(let iter = 0; iter < arr.length - 1; iter++) {
3 for(let index = 0; index < arr.length - 1 - iter; index++) {
4 if(arr[index] > arr[index + 1]) {
5 [arr[index], arr[index + 1]] = [arr[index + 1], arr[index]];
6 }
7 }
8 }
9 return arr;
10}

성능

NameBestAverageWorstStableIn-place
Bubble SortO(N2)O(N^2)O(N2)O(N^2)O(N2)O(N^2)YesYes

Best case 성능을 개선하기 위해서는 이번 회전에서 교환이 발생했는지 안했는지 검사한 후, 교환이 한 번도 발생하지 않았다면 바로 정렬을 끝내면 된다. 이렇게 되면 best case는 O(N)O(N)이 된다.

Inplace? 정렬을 위해 추가적인 메모리 공간이 거의 안드는 정렬을 의미한다.

Stable? 정렬했을 때 중복된 값들의 순서가 변하지 않음을 의미한다.

장단점

거품 정렬은 구현이 매우 간단하다는 장점 외에는 좋은 점이 하나도 없다.

알고리즘을 최적화하지 않는다면 best, average, worst case가 모두 O(N2)O(N^2)의 시간복잡도를 갖는 비효울적인 알고리즘이다. 또한 원소가 자기 자리를 찾아가기 위해 굉장히 많은 교환 연산이 필요하다.

Selection Sort(선택 정렬)

선택 정렬은 해당 순서에 넣을 원소를 찾아 넣어 정렬하는 알고리즘이다.

맨 처음부터 시작해서 배열의 가장 앞 순서에 와야할 원소를 찾아 맨 앞과 교체하고, 그 다음부터 다시 시작해서 정렬이 완료될 때까지 반복한다.

구현

1function selectionSort(arr) { // ascending order
2 for(let target = 0; target < arr.length - 1; target++) {
3 let minIndex = target;
4 for(let index = target + 1; index < arr.length; index++) {
5 if(arr[minIndex] > arr[index]) minIndex = index;
6 }
7 [arr[target], arr[minIndex]] = [arr[minIndex], arr[target]];
8 }
9 return arr;
10}

성능

NameBestAverageWorstStableIn-place
Selection SortO(N2)O(N^2)O(N2)O(N^2)O(N2)O(N^2)NoYes

매 반복마다 주어진 배열 전체를 비교하기 때문에 best, average, worst case 모두 O(N2)O(N^2)의 시간복잡도를 가진다.

장단점

버블 정렬과 마찬가지로 구현이 매우 단순하다.

선택 정렬도 버블 정렬과 같이 O(N2)O(N^2)의 시간복잡도를 가지지만, 비교 횟수에 비해 실제로 교환 연산은 적기 때문에 버블 정렬보다 대부분 빠르게 동작한다.

하지만 비효율적인건 마찬가지다.

그리고 unstable하다는 단점을 가진다.

예를 들어, [4, 3, 2, 4, 1]을 정렬한다고 해보자. 첫 번째 반복에서 1이 앞으로 옮겨져 [1, 3, 2, 4, 4]가 된다. 앞의 4가 뒤의 4보다 뒤로가면서 중복된 값의 순서가 변경됐다.

Insertion Sort(삽입 정렬)

삽입 정렬은 모든 요소를 앞에서부터 차례대로 이미 정렬된 부분과 비교해서 자신의 위치를 찾아 삽입하는 알고리즘이다.

두 번째 요소부터 시작해서 그 앞의 원소들과 비교해 삽입할 위치를 지정해 삽입하고, 이것을 반복한다.

구현

1function insertionSort(arr) { // ascending order
2 for(let start = 1; start < arr.length; start++) {
3 const elem = arr[start];
4 let index = start - 1;
5 while (target >= 0 && arr[target] > elem) {
6 arr[target + 1] = arr[target];
7 target--;
8 }
9 arr[target + 1] = elem;
10 }
11 return arr;
12}

성능

NameBestAverageWorstStableIn-place
Insertion SortO(N)O(N)O(N2)O(N^2)O(N2)O(N^2)YesYes

배열이 이미 정렬되어있는 경우 요소의 이동없이 한 번의 비교만 이루어지기 때문에 O(N)O(N)의 시간복잡도를 가진다.

장단점

구현이 간단하고 선택정렬과 버블정렬에 비해 빠르다는 장점을 가진다. 또한, 다른 정렬 알고리즘들과 다르게 정렬 중 데이터를 추가해도 상관없다.

하지만, 배열의 크기가 커지면 마찬가지로 비효율적이다.

Quick Sort(퀵 정렬)

퀵 정렬은 분할 정복을 통해 정렬을 수행한다.

  1. 배열에서 요소 하나를 고른다(=pivot).
  2. Pivot보다 작은 요소를 좌측으로, 큰 요소를 우측으로 재배치해 배열을 둘로 나눈다. 분할 이후 pivot은 움직이지 않는다.
  3. 분할된 두 배열에 대해 재귀적으로 이 과정을 반복한다.

구현

1function quickSort(arr) { // ascending order
2 function sort(arr, left, right) {
3 if(left >= right) return;
4 const pivot = partition(arr, left, right);
5 sort(arr, left, pivot - 1);
6 sort(arr, pivot + 1, right);
7 }
8
9 function partition(arr, left, right) {
10 // right is pivot
11 const pivot = right, pivotVal = arr[right];
12 while(left < right) {
13 while(pivotVal > arr[left]) left++;
14 while(left < right && pivotVal <= arr[right]) right--;
15 [arr[left], arr[right]] = [arr[right], arr[left]];
16 }
17 [arr[right], arr[pivot]] = [arr[pivot], arr[right]];
18 return right;
19 }
20
21 sort(arr, 0, arr.length - 1);
22 return arr;
23}

성능

NameBestAverageWorstStableIn-place
Quick SortO(NlogN)O(NlogN)O(NlogN)O(NlogN)O(N2)O(N^2)NoYes

퀵 정렬은 대개 매우 좋은 성능을 보여주지만, 배열의 최대값/최소값을 pivot으로 선택하여 분할이 되지 않은 경우 O(N2)O(N^2)의 시간복잡도를 가진다.

이를 피하기 위해 배열의 끝값과 중간값을 바꿔주면 확률적으로나마 시간복잡도를 개선할 수는 있지만, worst case를 O(NlogN)O(NlogN)으로 보장하지는 않는다.

장단점

다른 NlogNNlogN 정렬 알고리즘과 비교했을때 가장 속도가 빠르다는 장점을 가진다. 또한 정렬을 위한 추가 메모리 공간을 필요로 하지 않는다(in-place).

단점으로는 unstable하다는 점과 정렬된 배열에 대해서는 불균형 분할 때문에 오히려 시간이 더 걸린다는 것이다.

Merge Sort(병합 정렬)

병합 정렬도 분할 정복을 통해 정렬을 수행한다.

  1. 배열을 같은 크기의 2개의 배열로 분할한다.
  2. 각 배열을 정렬한다.
  3. 정렬된 배열을 하나의 배열로 병합(merge)한다.

구현

1function mergeSort(arr) {
2 function sort(arr) {
3 if(arr.length <= 1) return arr;
4 const middleIndex = Math.floor(arr.length / 2);
5
6 const leftSortedArr = sort(arr.slice(0, middleIndex));
7 const rightSortedArr = sort(arr.slice(middleIndex));
8
9 return merge(leftSortedArr, rightSortedArr);
10 }
11
12 function merge(leftArr, rightArr) {
13 const mergedArr = [];
14 let left = 0, right = 0;
15 while(left < leftArr.length && right < rightArr.length) {
16 let minElem = leftArr[left] <= rightArr[right] ? leftArr[left++] : rightArr[right++];
17 mergedArr.push(minElem);
18 }
19 return mergedArr.concat(leftArr.slice(left), rightArr.slice(right));
20 }
21
22 return sort(arr);
23}

성능

NameBestAverageWorstStableIn-place
Merge SortO(NlogN)O(NlogN)O(NlogN)O(NlogN)O(OlogN)O(OlogN)YesNo

병합 과정에서 배열의 길이만큼 메모리가 필요하기 때문에 in-place 정렬이 아니다.

만약 배열을 연결 리스트로 구현하면 in-place 정렬로 구현할 수 있다. 링크 인덱스만 변경돼서 데이터의 이동은 무시할 수 있을 정도로 작아지기 때문이다.

장단점

퀵 정렬과는 다르게 데이터의 분포가 정렬 시간에 영향을 덜 끼치고, 안정적(stable)이다.

병합 과정이 순차적인 비교로 진행되게 때문에 연결 리스트의 정렬에 매우 효율적이다.

단점으로는 배열의 크기가 클 경우 원소들의 이동횟수가 많아 느리다.

Heap Sort(힙 정렬)

힙 정렬은 '힙 자료구조'를 사용해 정렬을 수행한다.

힙에 대한 자세한 내용은 여기를 참고하자.

아이디어는 아주 간단하다.

모든 요소들을 힙에 넣은 후 다시 모든 요소들을 꺼내 반환 순서대로 배열하면 정렬 결과가 된다.

구현

1function heapSort(arr) { // ascending order
2 const minHeap = new MinHeap();
3 arr.forEach(elem => minHeap.push(elem));
4 arr.forEach((_, i) => arr[i] = minHeap.pop());
5 return arr;
6}

위에서 구현한 힙 정렬은 in-place가 아니지만, 배열을 힙으로 만드는 heapify 알고리즘을 사용하면 in-place로 구현할 수 있다.

heapify을 통해 배열을 힙으로 만든다. 이때 힙에서 요소 하나를 꺼내면 힙을 담은 배열의 맨 뒤쪽에 한 칸이 비는데, 여기에 꺼낸 요소를 옮기면 추가 메모리를 사용하지 않게 된다.

1function heapify(arr, size, here) {
2 let next = here;
3 let left = next * 2 + 1, right = next * 2 + 2;
4
5 if(left < size && arr[left] > arr[next]) next = left;
6 if(right < size && arr[right] > arr[next]) next = right;
7
8 if(here !== next) {
9 [arr[here], arr[next]] = [arr[next], arr[here]];
10 heapify(arr, size, next);
11 }
12}
13
14function heapSortInplace(arr) {
15 // 주어진 배열 힙 구조로 만들기
16 let mid = Math.floor(arr.length / 2 - 1); // 완전 이진 트리의 성질에 의해 중간 노드부터 자식이 있다.
17 while(mid >= 0) heapify(arr, arr.length, mid--);
18
19 // 루트를 빼며 정렬
20 let index = arr.length - 1;
21 while(index) {
22 [arr[index], arr[0]] = [arr[0], arr[index]];
23 heapify(arr, index--, 0);
24 }
25
26 return arr;
27}

성능

NameBestAverageWorstStableIn-place
Heap SortO(NlogN)O(NlogN)O(NlogN)O(NlogN)O(OlogN)O(OlogN)NoYes

장단점

가장 큰 값 혹은 가장 작은 값을 구할 때 유용하다. 그리고 heapify를 통해 구현할 경우 추가적인 메모리가 필요없다는 장점을 가진다.

Unstable하다는 것이 단점이다.

Counting Sort(계수 정렬)

계수 정렬은 이름처럼 배열 안의 각 요소의 수를 세서 정렬하는 방법이다.

요소들의 키 값을 세서 각 키 당 몇 개의 요소가 있는지 확인하고 이를 통해 각 키의 위치를 알 수 있다.

[1, 4, 2, 1]를 보자. 1이 2개, 2가 1개, 4가 1개다. 1이 2개이므로 1을 두 개 채워넣고, 그 다음 2를 1개, 4를 1개 채워넣으면 오름차순으로 정렬된 배열 [1, 1, 2, 4]를 만들 수 있다.

알고리즘의 단계는 다음과 같다(오름차순 기준).

  1. 요소를 세기 위한 배열을 잡고 각 요소의 수를 센다.
  2. 요소를 센 배열을 누적합으로 바꿔준다.
  3. 원래 배열을 순회하며 요소를 센 배열을 통해 위치를 찾아 결과 배열에 넣는다.

구현

1function countingSort(arr) {
2 const count = Array(Math.max(...arr) + 1).fill(0);
3 // 1. 세기
4 arr.forEach(element => count[element]++);
5 // 2. 누적합으로 바꿔주기
6 for(let index = 1; index < count.length - 1; index++) {
7 count[index] += count[index - 1];
8 }
9 // 3. 각 요소를 맞는 순서에 넣기
10 const sorted = Array(arr.length);
11 arr.forEach(element => {
12 sorted[count[element]++] = element;
13 });
14
15 return sorted;
16}

성능

NameBestAverageWorstStableIn-place
Counting SortO(N+K)O(N + K)O(N+K)O(N + K)O(N+K)O(N + K)YesNo

여기서 K는 배열의 최대값이다. K가 만약 작은 수면 시간복잡도는 O(N)O(N)에 가까워지지만, 반대로 매우 큰 수가 되면 O(N!)O(N!)이 될 수도 있다. 예를 들어 10개의 수를 정렬하는데 가장 큰 값이 100이면 O(N2)O(N^2), 1000이면 O(N3)O(N^3)이 된다.

이때까지 봤던 정렬 알고리즘들은 모두 비교를 통해 정렬을 했지만, 계수 정렬은 요소의 키 값으로 위치를 찾기 때문에 비교 정렬이 아니다. 따라서 비교 정렬 알고리즘의 lower bound인 O(NlogN)O(NlogN)가 적용되지 않는다.

장단점

정렬해야하는 요소들의 키 값의 범위가 작으면 빠르게 정렬할 수 있다.

하지만 범위가 크다면 성능이 크게 저하된다. 또한 요소를 세는 배열과 정렬된 배열을 추가적으로 생성해야하기 때문에 메모리 낭비가 심하다.

Radix Sort(기수 정렬)

기수 정렬은 기수 별로 비교없이 정렬하는 방법이다. 여기서 기수는 숫자의 자릿수를 의미한다.

가장 낮은 자리수부터 높은 자리수까지 버킷(bucket)을 이용하거나 위에서 봤던 counting sort(계수 정렬)을 이용해 정렬하면 된다.

버킷은 큐라고 생각하면 된다. 즉, 해당 자릿수의 숫자를 큐에 담은 후 낮은 수부터 순차적으로 빼주는 것이다.

기수 정렬은 최상위 유효숫자(Most Significant Digit)나 최하위 유효숫자(Least Significant Digit)에서 시작하도록 구현할 수 있다.

  • LSD 기수 정렬은 작은 자리수부터 정렬하기 때문에 마지막까지 정렬의 결과를 알 수 없다.
  • MSD 기수 정렬은 중간에 결과가 나올 수 있다. 마지막까지 비교를 하지 않아도 돼서 성능적인 이득을 취할 수 있지만 단점도 존재한다. 모든 데이터에 일관적인 과정을 거치게 할 수 없다는 것이다. 중간과정마다 데이터를 점검하지 않으면 오류가 발생할 수 있다. 이 때문에 추가적인 연산과 별도의 메모리가 필요해 성능적 이점도 사라질 수 있다.

일반적으로 MSD를 통한 구현이 난이도가 높기 때문에 LSD를 사용한다.

구현

1function radixSortBucket(arr) {
2 const longestRadix = Math.log10(Math.max(...arr)) + 1;
3
4 const sortByRadix = (arr, radix) => {
5 const exp = 10 ** radix;
6 const buckets = Array.from(Array(10), () => []);
7 // 각 요소를 알맞는 버킷에 삽입
8 arr.forEach(element => buckets[Math.floor((element / exp) % 10)].push(element));
9
10 // 버킷에서 순서대로 빼줌
11 let index = 0;
12 buckets.forEach(bucket => {
13 while(bucket.length) arr[index++] = bucket.shift();
14 });
15 }
16
17 for(let radix = 0; radix < longestRadix; radix++) {
18 sortByRadix(arr, radix);
19 }
20 return arr;
21}

Counting sort를 사용하고 싶다면 sortByRadix 부분만 바꿔주면 된다.

성능

NameBestAverageWorstStableIn-place
Counting SortO(NK)O(N * K)O(NK)O(N * K)O(NK)O(N * K)YesNo

K는 가장 큰 기수를 의미한다.

장단점

문자열과 정수와 같이 특정 자료형에 대해 정렬을 매우 빠르게 수행할 수 있다. 자릿수가 없는 부동 소수점 실수 같은 것들은 정렬할 수가 없다.

또한 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다.


참조:
https://github.com/trekhleb/javascript-algorithms
https://gmlwjd9405.github.io/tags#sort
https://gyoogle.dev/blog/