정렬 알고리즘(Sorting Algorithm) 정복하기 - with JS

안녕하세요. 동쪽별입니다.

이번 포스트에서는 여러 정렬 알고리즘에 대해 살펴보고, 자바스크립트로 구현해보도록 하겠습니다.

---

목차

1. 거품 정렬(Bubble Sort)
2. 선택 정렬(Selection Sort)
3. 삽입 정렬(Insertion Sort)
4. 퀵 정렬(Quick Sort)
5. 병합 정렬(Merge Sort)
6. 힙 정렬(Heap Sort)
7. 계수 정렬(Counting Sort)
8. 기수 정렬(Radix sort)

 

---

 

시작하기 전에 먼저, 정렬의 Stable 정렬과 In-place 정렬에 대해 알고 갑시다!

 

Stable 정렬?

정렬을 했을 때 중복된 값들의 순서가 변하지 않는 것을 말합니다.

만약, arr = [1, 7(1), 3, 5, 4, 7(2), 9] 을 정렬한 결과가

• arr = [1, 3, 4, 5, 7(1), 7(2), 9] 이면 Stable(안정)
• arr = [1, 3, 4, 5, 7(2), 7(1), 9] 이면 Unstable(불안정)

이라 할 수 있습니다. 

 

In-place 정렬?

정렬하는데 추가적인 메모리 공간이 거의 들지 않는 것을 말합니다.

제자리 정렬이라고도 합니다.

 

여러 정렬 알고리즘을 살펴보면서 Stable 여부, In-place 여부에 대해서도 살펴보도록 합시다.

 

---

거품 정렬(Bubble Sort)

 

버블 정렬은 첫번째 원소부터 인접한 원소와 비교하며 자리를 바꾸면서 맨 끝부터 정렬하는 방식입니다.

• i번째 원소와 i+1번째 원소의 값을 비교하고 만약 i번째의 값이 i+1번째의 값보다 크다면 둘의 자리를 바꾸어 값이 큰 원소가 뒤에 위치하게 합니다.
• 이를 반복해서 수행하면 가장 큰 값부터 뒤쪽에 쌓이게 되겠죠.
• 즉 가장 큰값을 하나씩 뒤로 보내면서 뒤쪽부터 정렬하는 것입니다.

 

이처럼 정렬 방식이 마치 물속에서 올라오는 물방울과 같다고 하여 버블 정렬이라는 이름이 붙여졌습니다.

 

function bubbleSort(arr) {
  for (let x = 0; x < arr.length; x++) {
    for (let y = 1; y < arr.length - x; y++) {
      if (arr[y - 1] > arr[y]) {
        [arr[y - 1], arr[y]] = [arr[y], arr[y - 1]];
      }
    }
  }

  return arr;
}

 

⏱ 시간 복잡도

• 시간 복잡도를 계산하면, (n-1) + (n-2) + (n-3) + .... + 2 + 1 = n(n-1) / 2 이므로 O(n^2) 입니다.
• 또한, 어떠한 경우에도 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간복잡도가 O(n^2) 으로 동일합니다.

 

👍 장점

• 구현이 매우 간단하고, 소스코드가 직관적입니다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로 In-place 정렬입니다.
• Stable 정렬입니다.

 

👎 단점

• 시간 복잡도가 최악, 최선, 평균 모두 O(n^2)으로, 굉장히 비효율적입니다.
• 데이터를 하나씩 비교하기 때문에 비교 횟수가 많아지므로 시간이 오래 걸리기 때문이죠.
• 정렬된 상태에서 새로운 데이터가 추가되면 정렬 효율이 좋지 않습니다.

 

➕ 개선

칵테일 셰이커(Cocktail Shaker) 정렬 (= 양방향 버블 정렬)

• 버블 정렬과는 달리 매 반복마다 배열의 순서를 바꾸어 정렬합니다.
• 홀수 번째 반복은 가장 작은 요소를 맨 앞으로, 짝수 번째 반복은 가장 큰 요소를 맨 뒤로 정렬합니다. (또는 반대)
• 시간복잡도는 최선의 경우 O(n)을 만족합니다!
• 평균과 최악의 경우 여전히 O(n^2) 입니다..

 

---

선택 정렬(Selection Sort)

 

선택 정렬은 앞쪽부터 정렬하는 방식입니다.

• 주어진 배열에서 가장 작은 최소값을 찾고 배열의 맨 앞의 값과 위치를 바꾸면서 정렬합니다.
• 맨 앞의 값을 제외한 배열로 다시 반복합니다.

 

선택 정렬은 배열의 최솟값을 찾아 선택하여 정렬한다는 뜻에서 이름이 붙여졌습니다. 배열에서 최솟값을 찾아야 하기 때문에 비교 횟수는 많지만 실제로 값을 바꾸는 교환 횟수가 적다는 것이 특징입니다

 

function selectionSort(arr) {
  let indexMin;
  for (let x = 0; x < arr.length - 1; x++) {
    indexMin = x;
    for (let y = x + 1; y < arr.length; y++) {
      if (arr[y] < arr[indexMin]) {
        indexMin = y;
      }
    }
    [arr[x], arr[indexMin]] = [arr[indexMin], arr[x]];
  }
  return arr;
}

 

⏱ 시간 복잡도

• (n-1) + (n-2) + .... + 2 + 1 = n(n-1) / 2 이므로 시간 복잡도는 O(n^2) 입니다.
• 최선, 평균, 최악의 경우 모두 시간복잡도가 O(n^2) 으로 동일합니다.

 

👍 장점

• 버블 정렬과 마찬가지로 구현이 간단합니다.
• 비교하는 횟수에 비해 교환하는 횟수가 적기 때문에, 많은 교환이 일어나야 하는 자료 상태에서 비교적 효율적입니다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로 In-place 정렬입니다.

 

👎 단점

• 데이터를 하나씩 비교하기 때문에 시간복잡도가 O(n^2)으로, 비효율적입니다.
• Unstable 정렬입니다. (구현하는 방식에 따라 달라질 수 있음)
• 정렬된 상태에서 새로운 데이터가 추가되면 정렬 효율이 좋지 않습니다.

 

---

삽입 정렬(Insertion Sort)

 

삽입 정렬은 버블 정렬의 비효율성을 개선하기 위해 등장한 방법입니다.

버블 정렬은 i번째와 i+1번째를 비교하며 위치를 바꾸었다면, 삽입 정렬은 i번째 원소를 정렬된 상태의 앞부분과 비교하여 적절한 위치에 삽입하는 방식입니다.

• i-1번째 원소까지는 모두 정렬된 상태여야 하며 i-1번째부터 0번째까지의 원소와 i번째 원소를 각각 비교합니다.
• 이때 i번째 원소보다 작은 값이 발견되면 그 위치에 i번째 원소를 삽입합니다.

 

삽입 정렬은 버블 정렬의 비교 및 교환 횟수를 줄임으로써 높은 효율을 보여줍니다.

 

function insertionSort(arr) {
  for (let x = 1; x < arr.length; x++) {
    let value = arr[x];
    let prev = x - 1;
    while (prev >= 0 && arr[prev] > value) {
      arr[prev + 1] = arr[prev];
      prev--;
    }
    arr[prev + 1] = value;
  }

  return arr;
}

 

⏱ 시간 복잡도

• 최악의 경우(역으로 정렬되어 있을 경우), (n-1) + (n-2) + .... + 2 + 1 = n(n-1 )/ 2 으로 O(n^2) 입니다.
• 하지만 모두 정렬이 되어있는 경우, 한번씩 밖에 비교를 안하므로 O(n) 의 시간복잡도를 가지게 됩니다.
• 즉, 최선의 경우 = O(n), 평균과 최악의 경우 = O(n^2) 입니다.

 

👍 장점

• 입력으로 들어오는 배열의 원소가 정렬되어있을수록 속도가 빠릅니다.
• 정렬된 값은 교환이 일어나지 않습니다.
• 그렇기 때문에, 이미 정렬되어 있는 배열에 자료를 하나씩 삽입/제거하는 경우에는 현실적으로 최고의 정렬 알고리즘이 됩니다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로 In-place 정렬입니다.
• Stable 정렬입니다.
• 선택 정렬, 버블 정렬과 같은 O(n^2) 알고리즘에 비교하여 상대적으로 빠릅니다.

 

👎 단점

• 평균과 최악의 시간복잡도가 O(n^2)으로 비효율적입니다.
• 선택 정렬, 버블 정렬과 마찬가지로 배열의 길이가 길어질수록 비효율적입니다.

 

❗️ 선택 정렬과 삽입 정렬을 헷갈리지 마세요!

• 선택 정렬과 삽입 정렬은 i번째 반복 이후, i 원소가 정렬된 순서로 온다는 점에서 유사합니다.
• 하지만, 선택 정렬은 i+1번째 원소를 찾기 위해 나머지 모든 원소들을 탐색하지만
• 삽입 정렬은 i+1번째 원소를 배치하는데 필요한 만큼의 원소만 탐색하기 때문에 훨씬 효율적으로 실행된다는 차이가 있습니다.

 

---

퀵 정렬(Quick Sort)

 

분할 정복(divide and conquer) 방법을 통한 정렬로, 하나의 pivot(축)을 정해서 이 pivot보다 작은 값은 왼쪽에 큰값은 오른쪽에 위치시키는 방법입니다.

• 왼쪽과 오른쪽에 해당하는 원소들에 대해 두 배열로 나눕니다. -> 분할(Divide)
• 분할된 두 개의 작은 배열에 대해 재귀(Recursion)적으로 이 과정을 반복합니다. 
• 재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있습니다.

실제로 많이 사용하고 있는 정렬 알고리즘으로 알려져 있습니다!

일반적으로 준수한 효율을 보이지만 최악의 경우에는 훨씬 많은 시간이 소요되므로 안정성이 좋지 않다는 특징이 있죠..

그럼에도 대부분의 내장 라이브러리에서 존재하는 정렬 함수는 퀵 정렬 알고리즘을 사용한답니다.

 

function quickSort(arr, left, right) {
  if (left >= right) {
    return;
  }

  /* 개선 방법
  const mid = (left + right) / 2;
  [arr[left], arr[mid]] = [arr[mid], arr[left]];
  */

  let pivot = arr[left];
  let x = left;
  let y = right;

  while (x < y) {
    while (pivot < arr[y]) {
      y--;
    }
    while (x < y && pivot >= arr[x]) {
      x++;
    }
    [arr[x], arr[y]] = [arr[y], arr[x]];
  }
  
  arr[left] = arr[x];
  arr[x] = pivot;

  quickSort(arr, left, x - 1);
  quickSort(arr, x + 1, right);

  return arr;
}

 

⏱ 시간 복잡도

• 최선과 평균의 경우 O(nlogn) 입니다.
• 최악의 경우(정렬이 되어 있는 경우) O(n^2) 입니다.

 

👍 장점

• 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환합니다.
• 한 번 결정된 pivot들이 추후 연산에서 제외되는 특성 때문에, 시간 복잡도 O(nlogn)을 가지는 다른 정렬 알고리즘과 비교했을 때 가장 빠릅니다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로 In-place 정렬입니다.

 

👎 단점

• 정렬된 배열에 대해서는 불균형 분할에 의해 오히려 수행시간이 더 많이 걸립니다.
• Unstable 정렬입니다. 

 

➕ 개선

• pivot 값이 최소나 최대값으로 지정되어(즉, 배열이 정렬되어 있으면) 파티션이 나누어지지 않을 때, O(n^2)에 대한 시간복잡도를 가지게 됩니다..
• 이때, 배열의 가장 앞에 있는 값과 중간값을 교환하여, 중간값이 pivot이 되도록 하면 확률적으로나마 시간복잡도를 O(nlogn)으로 개선할 수 있습니다.
• 말 그대로 확률적이기 때문에 반드시 개선되는 것은 아닙니다.

 

---

병합 정렬(Merge Sort)

 

병합 정렬은 배열을 작은 단위로 쪼개어 정렬한 결과를 합치면서 전체를 정렬하는 분할 정복(divide and conquer) 방식입니다. 

• 배열을 왼쪽 절반, 오른쪽 절반으로 분할하며 최소 단위로 쪼갠 후 정렬을 진행합니다.
• 쪼갠 영역들(이미 정렬이 되어 있습니다)을 차례대로 두개씩 병합(merge)합니다.

빠른 정렬로 분류되며, 퀵 정렬과 함께 많이 언급되는 정렬 방식입니다.

 

function merge(leftArr, rightArr) {
  const sortedArr = [];
  let l = 0;
  let r = 0;

  while (l < leftArr.length && r < rightArr.length) {
    if (leftArr[l] <= rightArr[r]) {
      sortedArr.push(leftArr[l]);
      l++;
    } else {
      sortedArr.push(rightArr[r]);
      r++;
    }
  }
  
  while (l < leftArr.length) {
    sortedArr.push(leftArr[l]);
    l++;
  }

  while (r < rightArr.length) {
    sortedArr.push(rightArr[r]);
    r++;
  }

  return sortedArr;
}

function mergeSort(arr) {
  if (arr.length === 1) {
    return arr;
  }

  const mid = Math.ceil(arr.length / 2);

  const leftArr = arr.slice(0, mid);
  const rightArr = arr.slice(mid);

  return merge(mergeSort(leftArr), mergeSort(rightArr));
}

 

⏱ 시간 복잡도

• 최선, 평균, 최악 모두 O(nlogn)입니다.
• 분할할 때 걸리는 시간은 O(n), 병합에 걸리는 시간은 O(n), 그리고 레벨의 수가 O(logn)이므로 전체 레벨의 병합에 걸리는 총시간은 O(nlogn)입니다.

 

👍 장점

• 항상 일정한 시간 복잡도 O(nlogn)를 가집니다.
• Stable 정렬입니다.

 

👎 단점

• 정렬을 하는 배열외의 추가적인 임시 배열 (추가적인 메모리)가 필요합니다.
• 정렬하고자 하는 배열의 크기만큼의 추가적인 크기가 요구되기 때문에 Not In-place 정렬입니다.

 

❗️ Linked List의 정렬에 사용하면 효율적입니다.

• 병합 정렬은 순차적인 비교를 진행하기 때문입니다.
• 반대로, 퀵 정렬은 순차 접근이 아닌 임의 접근이기 때문에 Linked List 정렬에는 비효율적입니다.

 

---

힙 정렬(Heap Sort)

 

힙 정렬은 최대 힙 트리(Max Heap Tree)나 최소 힙 트리(Min Heap Tree)를 구성하여 정렬하는 방식입니다.

• 힙(Heap)? 완전 이진 트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조
• 완전 이진 트리? 삽입할 때 왼쪽부터 차례대로 추가하는 이진 트리
• 최대 힙 트리? 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
• 최소 힙 트리? 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

 

• 먼저, 입력으로 들어오는 배열로 힙 트리를 만듭니다.
  • 내림차순으로 정렬하기 위해서는 최대 힙 트리를 구성하고 오름차순으로 구성하기 위해서는 최소 힙 트리를 구성합니다.
• 힙 트리로 구한 최댓값 혹은 최솟값에 해당하는 root 노드를 빼내면서 정렬을 수행합니다.

(아래는 in-place 정렬를 위한 과정입니다.)

• root 노드를 하나씩 꺼내어 배열의 뒤쪽부터 넣습니다.
• 빈 root 노드 자리에는 힙 트리의 가장 뒤에 있는 원소가 들어가서 자기 자리를 찾아갑니다.

힙 정렬은 여러 개의 값중에서 최댓값이나 최솟값을 빠르게 찾기 위해 사용됩니다.

 

(아래는 in-place 정렬을 위한 과정을 제외한 코드입니다.)

class Heap {
  constructor() {
    this.heap = [];
  }

  getLeftChild = (parent) => {
    return parent * 2 + 1;
  };

  getRightChild = (parent) => {
    return parent * 2 + 2;
  };

  getParent = (child) => {
    return Math.floor((child - 1) / 2);
  };

  insert = (key, value) => {
    const node = { key, value };
    this.heap.push(node);
    this.heapifyUp();
  };

  remove = () => {
    const count = this.heap.length;
    const root = this.heap[0];

    if (count <= 0) return;

    if (count === 1) {
      this.heap = [];
    } else {
      this.heap[0] = this.heap.pop();
      this.heapifyDown();
    }

    return root;
  };

  heapifyUp = () => {
    let index = this.heap.length - 1;
    const insertedNode = this.heap[index];

    while (index > 0) {
      const parent = this.getParent(index);

      if (this.heap[parent].key > insertedNode.key) {
        this.heap[index] = this.heap[parent];
        index = parent;
      } else {
        break;
      }
    }

    this.heap[index] = insertedNode;
  };

  heapifyDown = () => {
    let index = 0;
    const count = this.heap.length;
    const root = this.heap[index];

    while (this.getLeftChild(index) < count) {
      const leftChild = this.getLeftChild(index);
      const rightChild = this.getRightChild(index);

      let minChild;

      if (
        rightChild < count &&
        this.heap[rightChild].key < this.heap[leftChild].key
      ) {
        minChild = rightChild;
      } else {
        minChild = leftChild;
      }

      if (this.heap[minChild].key <= root.key) {
        this.heap[index] = this.heap[minChild];
        index = minChild;
      } else {
        break;
      }
    }

    this.heap[index] = root;
  };
}

function heapSort(arr) {
  const heap = new Heap();

  for (const element of arr) {
    heap.insert(element);
  }

  const sorted = [];

  while (heap.heap.length) {
    const { key } = heap.remove();
    sorted.push(key);
  }

  return sorted;
}

 

⏱ 시간 복잡도

• 최선, 평균, 최악 모두 O(nlogn)입니다.

 

👍 장점

• 가장 크거나 가장 작은 값을 구할 때 유용합니다. → 한번의 힙 구성을 통해 구하는 것이 가능합니다.
• 멀리 떨어진 요소들을 정렬할 때 유용합니다 → 삽입정렬보다 더욱 개선된 결과를 얻어낼 수 있습니다.
• 항상 같은 시간 복잡도를 가지기 때문에 성능이 준수합니다.
• 주어진 배열 내부에서 위치를 바꾸는 방식으로 하면 in-place 정렬이 가능합니다.

 

👎 단점

• 같은 시간 복잡도를 가지는 다른 정렬 알고리즘과 비교하면 느린 편입니다.
  • 퀵정렬과 합병정렬의 성능이 좋기 때문에 힙 정렬의 사용빈도가 높지는 않습니다.
• Unstable 정렬입니다.

 

---

 

O(n^2) 알고리즘은 자신의 옆에 수와 비교해야 하므로 O(n^2)의 한계를 벗어나지 못합니다.

O(nlogn) 알고리즘으로 자신의 옆에 수 말고, 건너건너 수와 비교하여 O(nlogn) 시간 복잡도를 달성할 수 있었지만,

어떤 수와 비교를 하여 정렬을 한다면 결국 O(nlogn) 시간을 벗어날 수 없다는 한계에 봉착하게 됩니다.

 

이제부터는 O(n) 정렬을 알아보도록 하겠습니다. 

O(n)이 어떻게 가능하냐고요? 비교를 하지 않기 때문입니다!

 

계수 정렬(Counting Sort)

계수 정렬은 각 항목을 세어 저장해두고, 이를 앞 순서대로 정렬하는 방식입니다.

• 예를 들어, [3,4,1,2,4,6,1] 배열을 정렬한다고 했을 때,
• 해당 배열에서 각 숫자가 몇 개 나오는 지 세어보면 아래와 같습니다.

1 : 2개
2 : 1개
3 : 1개
4 : 2개
6 : 1개

• 그리고 1부터 6까지 갯수대로 나열하는 것입니다. → [1,1,2,3,4,4,6]

요소 값들끼리 서로 비교하지 않고 정렬하는 것이죠.

 

이를 프로그래밍 로직으로 표현하면, 아래와 같습니다.

• 먼저, 배열 내에 원소 값들의 갯수를 저장하는 카운팅 배열을 만듭니다.
• 카운팅 배열의 요소들에 대해서 직전 요소들의 값을 더해줍니다. (누적합)
• 입력 배열과 동일한 크기의 출력 배열을 만들고, 입력 배열의 역순으로 출력 배열에 요소들을 채워 넣어줍니다.

 

이때, 아래의 제약사항이 존재합니다.

• 데이터(값)는 양수여야 합니다.
• 값의 범위가 너무 크지 않아야 합니다.

이유는 바로, 배열의 인덱스를 이용하여 데이터를 저장할 것이기 때문입니다.

배열의 인덱스는 양수만 존재하고, 값이 너무 커지면 메모리 영역을 너무 많이 할당해버려 문제가 생기므로 위의 두 조건이 붙게되는 것이죠.

 

function countingSort(arr) {
  // 배열의 사이즈를 최대값 9가 담기도록 크게 잡기
  const MAX_DATA_VALUE = 10;
  const counting = new Array(MAX_DATA_VALUE).fill(0);

  for (let i = 0; i < arr.length; i++) {
    counting[arr[i]]++;
  }

  for (let i = 1; i < MAX_DATA_VALUE; i++) {
    counting[i] += counting[i - 1];
  }

  const sorted = new Array(arr.length).fill(0);

  for (let i = arr.length - 1; i >= 0; i--) {
    sorted[counting[arr[i]] - 1] = arr[i];
    counting[arr[i]]--;
  }

  return sorted;
}

 

⏱ 시간 복잡도

• O(n + k)입니다.
• k는 정렬할 수들 중에 가장 큰 값을 의미합니다.
• 만약 k가 n보다 작은 수이면 O(n)이 되지만, k가 n보다 매우 큰 수이면 O(무한)이 될 수도 있습니다. 

 

👍 장점

• 정렬하는 숫자가 특정한 범위 내에 있을 때 유용합니다.
• 비교없는 O(n) 의 시간복잡도를 가집니다.
• 맨 뒤의 수부터 값을 채우기 때문 Stable 정렬입니다.
  • 만약 Unstable해도 상관없다면 앞에서부터 채워도 문제가 될 것은 없습니다.

 

👎 단점

• 입력 데이터의 최대값에 따라 카운팅 배열의 크기가 커집니다.
• 즉, 메모리 낭비가 심합니다.
• Not In-place 정렬입니다.

 

---

기수 정렬(Radix sort)

데이터의 각 자릿수를 낮은 자리수에서부터 가장 큰 자리수까지 올라가면서 정렬을 수행하는 방식입니다.

• 먼저, 최대 자릿수를 구합니다.
• 그리고 bucket 배열을 하나 만들어, 1의 자리가 같은 원소들을 생성한 배열에 모읍니다.
• 다음 같은 방식으로 10, 100 ... , 최대 자릿수까지 이를 반복합니다.

 

1의 자리

 

10의 자리

 

100의 자리

 

기수 정렬은 계수 정렬과 마찬가지로 비교연산을 수행하지 않아 조건이 맞는 상황에서 빠른 정렬 속도를 보장합니다.

또한, 입력 데이터의 최대값에 따른 계수 정렬의 비효율성을 개선하기 위해서, 기수 정렬을 사용할 수 있습니다. 자릿수의 값 별로 정렬을 하므로, 나올 수 있는 값의 최대 사이즈는 9이기 때문입니다.

 

function getMaxDigit(arr) {
  let maxDigit = 0;
  for (let i = 0; i < arr.length; i++) {
    maxDigit = Math.max(maxDigit, `${arr[i]}`.length);
  }
  return maxDigit;
}

function radixSort(arr) {
  const maxDigit = getMaxDigit(arr);

  for (let x = 0; x < maxDigit; x++) {
    let digitBucket = new Array(10).fill(0).map((_) => []);
    for (let i = 0; i < arr.length; i++) {
      let digit = Math.floor(Math.abs(arr[i]) / Math.pow(10, x)) % 10;
      digitBucket[digit].push(arr[i]);
    }
    arr = [].concat(...digitBucket);
  }

  return arr;
}

 

⏱ 시간 복잡도

• O(dn)입니다.
• d는 데이터들의 최대 자리수를 의미합니다.

 

👍 장점

• 비교없는 O(n) 의 시간복잡도를 가집니다.
• 문자열, 정수 정렬 가능합니다.
  • 음수가 있을 경우에는 음수를 따로 빼내서 똑같은 방법으로 정렬 한 후, 결과를 양수 결과랑 합치는 식으로 해야 합니다.
• Stable 정렬입니다.

 

👎 단점

• 자릿수가 없는 것은 정렬할 수 없습니다. (부동 소수점)
• 중간 결과를 저장할 bucket 공간이 필요합니다.
• Not In-place 정렬입니다.

 

❗️왜 낮은 자리수부터 정렬을 할까?

• LSD(Least Significant Digit): 가장 작은 자릿수부터 정렬을 진행해 나가는 방식
  • 마지막까지 결과를 알 수 없는 것이 이 방법의 단점입니다.
  • 그러나 구현이 간단하다는 장점이 있습니다.
  • LSD는 자릿수가 정해진 경우 좀 더 빠를 수도 있습니다.
• MSD(Most Significant Digit): 가장 큰 자릿수부터 정렬을 진행해 나가는 방식
  • 반드시 끝까지 가지 않아도 중간에 정렬이 완료될 수 있다는 것이 이 방법의 장점입니다.
  • 그러나 중간에 데이터를 점검해야 합니다.
    • 코드를 추가해야하므로 구현이 복잡해집니다.
    • 중간에 데이터를 점검해야 하므로 성능의 이점도 반감될 수 있습니다.

 

→ MSD의 경우 정렬의 과정이 단축될 수 있어서 성능의 향상을 조금 기대할 수 있지만, 추가적인 연산과 별도의 메모리가 요구됩니다.

→ 따라서, 일반적인 상황이라면 LSD 방식을 이용합니다.

 

 

 

.

.

.

 

 

 

다양한 정렬 알고리즘을 알아보았습니다.

정렬은 알고리즘의 기본 중의 기본!

정렬 알고리즘을 함께 정복합시다 😁

 

 

※ 참조

👨🏻‍💻 Tech Interview

[Algorithm] 여러 정렬 알고리즘의 특징과 복잡도

알고리즘 6일차 - O(n) 정렬, 계수 정렬

[알고리즘 정리] 기수정렬(Radix Sort)