정렬 알고리즘 (Sorting Algorithms)

Sorting Algorithms

정렬(Sorting)은 가장 기본적인 알고리즘이지만, 활용할 수 있는 영역이 무수히 많습니다. 대표적인 예로 내가 만든 블로그 서비스를 이용하는 사용자가 게시된 글을 최신순으로 보고 싶어 한다면, 날짜별로 정렬해서 제공하면 됩니다. 이처럼 데이터베이스에 저장된 데이터는 서비스와 함께 제공하는 경우가 많은데, 데이터에 대해 정렬을 하게 되면 탐색 시 간편하면서도 효율적인 접근이 가능해집니다.

본문에서는 버블 정렬부터 현대 프로그래밍 언어에서 채택해 사용하고 있는 팀 정렬까지 총 11가지 알고리즘에 대해 간단히 소개합니다.

알고리즘 동작에 대한 이해를 돕기 위해 동영상을 함께 첨부했습니다 🙂

01. 버블 정렬 (Bubble Sort)

버블 정렬은 데이터 집합을 순회할 때, 좌우의 값을 비교하면서 정렬하는 알고리즘입니다. 정렬 알고리즘 중 구현이 간단한 편에 속하지만, 기본적으로 이중 반복문을 통해 정렬하기 때문에 평균 속도가 빠르지는 않습니다.

const bubbleSort = (arr) => {
  // 정렬이 필요 없는 경우
  let needSort = false;
  for (let i = 1; i < arr.length; i++) {
    if (arr[i - 1] > arr[i]) {
      needSort = true;
    }
  }
  if (!needSort) return;

  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
};

const arr = [1, 5, 4, 2, 3];

console.log(arr);
bubbleSort(arr);
console.log(arr);

성능 평가 (Big-O)

• [시간 복잡도] 최선: O(N)
• [시간 복잡도] 평균: O(N^2)
• [시간 복잡도] 최악: O(N^2)
• [공간 복잡도] 최악: O(1)

02. 선택 정렬 (Selection Sort)

선택 정렬은 순회 중인 요소의 인덱스와 최솟값을 가진 요소의 인덱스를 가지고 정렬을 수행합니다. 순회 중인 요소의 인덱스를 최솟값이라 가정하고 저장해 둔 다음, 내부에 반복문을 하나 더 돌리면서 남은 요소 중 최솟값이 존재하는지 찾습니다. 그렇게 최솟값이 존재하면 인덱스가 갱신되어, 인덱스 간의 값이 달라지기 때문에 이를 기반으로 정렬할 수 있습니다.

const selectionSort = (arr) => {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIndex = i;

    for (let j = i + 1; j < arr.length; j++) {
      if (arr[minIndex] > arr[j]) minIndex = j;
    }

    if (i !== minIndex) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
};

const arr = [1, 5, 4, 2, 3];

console.log(arr);
selectionSort(arr);
console.log(arr);

성능 평가 (Big-O)

• [시간 복잡도] 최선: O(N^2)
• [시간 복잡도] 평균: O(N^2)
• [시간 복잡도] 최악: O(N^2)
• [공간 복잡도] 최악: O(1)

03. 삽입 정렬 (Insertion Sort)

삽입 정렬은 어떤 요소를 뽑은 다음 나머지 요소들과 비교하여 더 큰 값이 있다면 오른쪽으로 한 칸씩 밀어 넣습니다. 그리고 더 이상 밀어 넣을 값이 없다면, 해당 자리가 비어 있기 때문에 그 자리에 요소를 배치합니다. 나머지 요소들도 동일한 과정을 거치게 되며, 모든 과정이 끝나면 정렬이 마무리 됩니다. 

const insertionSort = (arr) => {
  for (let i = 1; i < arr.length; i++) {
    if (arr[i - 1] <= arr[i]) continue;

    for (let j = i; j > 0; j--) {
      if (arr[j - 1] > arr[j]) {
        [arr[j - 1], arr[j]] = [arr[j], arr[j - 1]];
      }
    }
  }
};

const arr = [1, 5, 4, 2, 3];

console.log(arr);
insertionSort(arr);
console.log(arr);

성능 평가 (Big-O)

• [시간 복잡도] 최선: O(N)
• [시간 복잡도] 평균: O(N^2)
• [시간 복잡도] 최악: O(N^2)
• [공간 복잡도] 최악: O(1)

04. 셸 정렬 (Shell Sort)

셸 정렬은 삽입 정렬의 장점은 수용하고, 단점은 보완한 알고리즘입니다. 정렬 시 갭(Gap)이라고 하는 것을 사용해, 일정 거리의 요소들하고만 비교를 합니다. 예를 들어 갭의 크기가 2라면, 두 칸 씩 떨어진 요소들과만 비교를 하는 것입니다. 삽입 정렬에 비해 정렬 횟수는 늘었지만, 전체적으로 요소의 이동 횟수는 줄어들어 효율적입니다.

const shellSort = (arr) => {
  let len = arr.length;

  for (let gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
    for (let i = gap; i < len; i += 1) {
      let temp = arr[i];
      let j;

      for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
        arr[j] = arr[j - gap];
      }
      arr[j] = temp;
      console.log(arr);
    }
  }
};

const arr = [1, 5, 4, 2, 3];

console.log(arr);
shellSort(arr);
console.log(arr);

성능 평가 (Big-O)

• [시간 복잡도] 최선: O(NlogN)
• [시간 복잡도] 평균: Gap 크기에 따라 결정
• [시간 복잡도] 최악: Gap 크기에 따라 결정
• [공간 복잡도] 최악: O(1)

05. 계수 정렬 (Count Sort)

계수 정렬은 도수분포표를 이용한 정렬 알고리즘입니다. 각 요소가 몇 개나 존재하는지 도수분포표에 기록하고, 이를 누적 도수분포표로 만들면 각 요소가 자리할 인덱스를 얻을 수 있습니다. 예를 들어 [1, 2, 1]이라는 배열을 정렬하고자 한다면, 도수분포표는 { 1: 2, 2: 1 }처럼 만들 수 있습니다. 그리고 이를 누적 도수분포표로 만들면 { 1: 2, 2: 3 }이 되어, 해당 요소를 어디서부터 배치하면 되는지 알 수 있습니다.

// 도수분포표 생성
const makeFTable = (arr) => {
  const fTable = {};

  arr.forEach((v) => {
    if (!fTable[v]) fTable[v] = 1;
    else fTable[v]++;
  });

  return fTable;
};

const countingSort = (arr, fTable) => {
  // 누적 도수분포표 생성
  Object.keys(fTable).reduce((sum, key) => {
    fTable[key] += sum;
    return fTable[key];
  }, 0);

  // 정렬
  const sorted = Array.from({ length: arr.length }, () => 0);
  arr.forEach((v) => {
    sorted[--fTable[v]] = v;
  });

  return sorted;
};

const arr = [1, 2, 5, 3, 4, 2, 6, 3];
const fTable = makeFTable(arr);

console.log(arr);
const sorted = countingSort(arr, fTable);
console.log(sorted);

성능 평가 (Big-O) // k = count of unique element

• [시간 복잡도] 최선: O(N+k)
• [시간 복잡도] 평균: O(N+k)
• [시간 복잡도] 최악: O(N+k)
• [공간 복잡도] 최악: O(k)

06. 기수 정렬 (Radix Sort)

기수 정렬은 숫자 타입으로 이루어진 데이터 집합에만 사용할 수 있는 정렬 알고리즘입니다. 각 숫자의 자릿수를 비교하는 방식으로 동작하는데, 일의 자리부터 비교하여 정렬하고, 그 다음에는 십의 자리를 비교하여 정렬하는 식입니다. 자릿수를 비교할 때는 모듈러 연산자(%)를 사용하면 되고, 각 자릿수를 정렬하는 단계에서는 앞서 소개한 계수 정렬을 사용하면 됩니다.

const countSort = (arr, n, exp) => {
  const temp = Array.from({ length: n }, () => 0);
  const count = Array.from({ length: 10 }, () => 0);

  arr.forEach((item) => count[Math.floor(item / exp) % 10]++);

  for (let i = 1; i < count.length; i++) {
    // 누적 도수분포표 생성
    count[i] += count[i - 1];
  }

  for (let i = n - 1; i >= 0; i--) {
    // 도수 분포표를 참조하여 인덱스를 계산
    temp[count[Math.floor(arr[i] / exp) % 10] - 1] = arr[i];
    count[Math.floor(arr[i] / exp) % 10]--;
  }

  // 기존 배열에 값 복사
  for (let i = 0; i < n; i++) arr[i] = temp[i];
};

const radixSort = (arr) => {
  // 가장 큰 값의 자릿수만큼 반복
  const max = arr.reduce((pre, cur) => (pre > cur ? pre : cur));
  for (let exp = 1; Math.floor(max / exp) >= 1; exp *= 10) {
    countSort(arr, arr.length, exp);
  }
};

const arr = [170, 45, 75, 90, 802, 24, 2, 66];

radixSort(arr);
console.log(arr);

성능 평가 (Big-O) // k = count of unique element

• [시간 복잡도] 최선: O(Nk)
• [시간 복잡도] 평균: O(Nk)
• [시간 복잡도] 최악: O(Nk)
• [공간 복잡도] 최악: O(N+k)

07. 피존홀 정렬 (Pigeonhole Sort)

피존홀 정렬은 피존홀이라는 데이터 집합을 이용한 정렬 알고리즘입니다. 피존홀 안에는 정렬하고자 하는 요소들이 알맞게 위치하게 되는데, 요소들의 인덱스는 [요소 - 최솟값]으로 결정됩니다. 계수 정렬과 비슷해 보이지만, 최솟값을 이용한 두 요소의 차를 인덱스로 이용했다는 것에서 차이가 있습니다.

const pigeonholeSort = (arr) => {
  const pigeonhole = {};
  let result = [];

  const min = Math.min(...arr);

  arr.forEach((item) => {
    const diff = item - min;
    if (pigeonhole[diff]) pigeonhole[diff].push(item);
    else pigeonhole[diff] = [item];
  });

  Object.keys(pigeonhole).forEach((key) => {
    result = result.concat(pigeonhole[key]);
  });

  return result;
};

const arr = [8, 3, 2, 7, 4, 6, 8];

console.log(pigeonholeSort(arr));

성능 평가 (Big-O) // n = input size

• [시간 복잡도] 최악: O(N+n)
• [공간 복잡도] 최악: O(N+n)

08. 병합 정렬 (Merge Sort)

병합 정렬은 데이터 집합을 앞부분과 뒷부분으로 나누어 정렬한 다음 병합하는 식으로 진행하는 정렬 알고리즘입니다. 대표적인 분할 정복(Divide and Conquer) 알고리즘입니다. 구현하는 코드가 분할하는 부분과 병합하는 부분이 나뉘어 있기 때문에, 비교적 길긴해도 천천히 살펴보면 크게 어려운 알고리즘은 아닙니다.

const mergeSort = (arr, left, right) => {
  if (left < right) {
    const center = Math.floor((left + right) / 2);
    const buff = [];
    let p = 0;
    let i;
    let j = 0;
    let k = left;

    mergeSort2(arr, left, center);
    mergeSort2(arr, center + 1, right);

    for (i = left; i <= center; i++) buff[p++] = arr[i];
    while (i <= right && j < p) arr[k++] = buff[j] <= arr[i] ? buff[j++] : arr[i++];
    while (j < p) arr[k++] = buff[j++];
  }
};

const arr = [7, 22, 5, 11, 32, 120, 68, 70];

mergeSort(arr, 0, arr.length - 1);
console.log(arr);

성능 평가 (Big-O)

• [시간 복잡도] 최선: O(NlogN)
• [시간 복잡도] 평균: O(NlogN)
• [시간 복잡도] 최악: O(NlogN)
• [공간 복잡도] 최악: O(N)

09. 퀵 정렬 (Quick Sort)

퀵 정렬은 이름 그대로 정말 빠르다 알려진 정렬 알고리즘입니다. 병합 정렬과 동일한 분할 정복 방식의 알고리즘이며, 기준이 되는 요소(pivot)를 정해 해당 요소보다 작은 값들은 왼쪽으로, 큰 값들은 오른쪽으로 몰아 넣으며 데이터 집합을 분할합니다. 기준 요소는 그대로 정렬이 된 것이기에, 분할된 집합들만 추가적으로 정렬해 나가면 됩니다.

const quickSort = (arr, start, end) => {
  if (start >= end) return;

  const pivot = start;
  let left = start + 1;
  let right = end;

  while (left <= right) {
    while (arr[left] <= arr[pivot]) left++;
    while (arr[right] > arr[pivot]) right--;

    if (left < right) [arr[left], arr[right]] = [arr[right], arr[left]];
    else [arr[pivot], arr[right]] = [arr[right], arr[pivot]];
  }

  quickSort(arr, start, right - 1);
  quickSort(arr, right + 1, end);
};

const arr = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8];

quickSort(arr, 0, arr.length - 1);
console.log(arr);

성능 평가 (Big-O)

• [시간 복잡도] 최선: O(NlogN)
• [시간 복잡도] 평균: O(NlogN)
• [시간 복잡도] 최악: O(N^2)
• [공간 복잡도] 최악: O(NlogN)

10. 힙 정렬 (Heap Sort)

힙 정렬은 루트 노드에 가장 큰 값이 존재하는 이진 트리인 힙(Heap)을 이용한 정렬 알고리즘입니다. 힙은 루트가 큰 값이기에 이 값을 순차적으로 빼기만 하면 정렬이 완료됩니다. 하지만 힙에서 루트를 빼는 순간 더 이상 힙이 아니기 때문에, 새로운 루트를 트리 안에서 찾은 다음 만들어 주는 작업을 해야 합니다.

파이썬과 달리 자바스크립트는 힙과 관련된 내장 라이브러리가 없어 클래스로 직접 구현했습니다.

class Heap extends Array {
  constructor({ type }) {
    super();
    this.usedSize = 0;
    this.type = type;
  }

  insert(newData) {
    let currentIndex = this.usedSize;
    let parentIndex = this.getParentIndex(currentIndex);

    this.push(newData);
    this.usedSize += 1;

    if (this.type === 'min') {
      // min-heap
      while (currentIndex > 0 && this[currentIndex] < this[parentIndex]) {
        this.swap(currentIndex, parentIndex);
        currentIndex = parentIndex;
        parentIndex = this.getParentIndex(currentIndex);
      }
    } else {
      // max-heap
      while (currentIndex > 0 && this[currentIndex] > this[parentIndex]) {
        this.swap(currentIndex, parentIndex);
        currentIndex = parentIndex;
        parentIndex = this.getParentIndex(currentIndex);
      }
    }
  }

  delete() {
    const deleteNode = this[0];
    this.usedSize -= 1;

    if (this.usedSize === 0) {
      this.pop();
      return deleteNode;
    } else {
      this[0] = this.pop();
    }

    // Reconstruct heap
    let parentIndex = 0;
    let leftChildIndex = this.getLeftChildIndex(parentIndex);
    let rightChildIndex = leftChildIndex + 1;

    while (true) {
      let selectedIndex;

      if (leftChildIndex >= this.usedSize) break;
      if (rightChildIndex >= this.usedSize) {
        selectedIndex = leftChildIndex;

        if (this.type === 'min') {
          if (this[selectedIndex] < this[parentIndex]) {
            this.swap(selectedIndex, parentIndex);
            parentIndex = selectedIndex;
          } else {
            break;
          }
        } else {
          if (this[selectedIndex] > this[parentIndex]) {
            this.swap(selectedIndex, parentIndex);
            parentIndex = selectedIndex;
          } else {
            break;
          }
        }
      } else {
        if (this.type === 'min') {
          if (this[leftChildIndex] < this[rightChildIndex]) selectedIndex = leftChildIndex;
          else selectedIndex = rightChildIndex;

          if (this[selectedIndex] < this[parentIndex]) {
            this.swap(selectedIndex, parentIndex);
            parentIndex = selectedIndex;
          } else {
            break;
          }
        } else {
          if (this[leftChildIndex] > this[rightChildIndex]) selectedIndex = leftChildIndex;
          else selectedIndex = rightChildIndex;

          if (this[selectedIndex] > this[parentIndex]) {
            this.swap(selectedIndex, parentIndex);
            parentIndex = selectedIndex;
          } else {
            break;
          }
        }
      }
      leftChildIndex = this.getLeftChildIndex(parentIndex);
      rightChildIndex = leftChildIndex + 1;
    }

    return deleteNode;
  }

  swap(index1, index2) {
    [this[index1], this[index2]] = [this[index2], this[index1]];
  }

  getParentIndex(index) {
    return Math.floor((index - 1) / 2);
  }

  getLeftChildIndex(index) {
    return index * 2 + 1;
  }
}

const heap = new Heap({ type: 'min' });
console.log(heap);
heap.insert(22);
heap.insert(5);
heap.insert(11);
heap.insert(32);
heap.insert(120);
heap.insert(68);
heap.insert(70);

console.log(heap);
while (heap.usedSize !== 0) {
  process.stdout.write(`${heap.delete()} `);
}
console.log();

성능 평가 (Big-O)

• [시간 복잡도] 최선: O(N)
• [시간 복잡도] 평균: O(NlogN)
• [시간 복잡도] 최악: O(NlogN)
• [공간 복잡도] 최악: O(N)

11. 팀 정렬 (Tim Sort)

팀 정렬은 안정적인 정렬 알고리즘인 삽입 정렬과 병합 정렬을 합친 알고리즘입니다. 삽입 정렬의 경우 시간 복잡도가 좋지 않지만, 정렬하고자 하는 요소의 개수가 적다면 좋은 퍼포먼스를 보입니다. 그래서 정렬하고자 하는 데이터 집합을 잘게 나눠, 나눈 조각들에 대해 각각 삽입 정렬로 정렬합니다. 이후에는 더 이상 삽입 정렬을 하지 않고 조각을 최대한 모아 병합 정렬로 마무리합니다.

팀 정렬은 안정적이면서도 속도 또한 빠르기 때문에 현대 프로그래밍 언어(파이썬, 자바, 자바스크립트 등)들의 정렬 알고리즘으로 채택되어 사용되고 있습니다.

const MIN_MERGE = 32;

const minRunLength = (n) => {
  let r = 0;
  while (n >= MIN_MERGE) {
    r |= n & 1;
    n >>= 1;
  }
  return n + r;
};

const insertionSort = (arr, left, right) => {
  for (let i = left + 1; i <= right; i++) {
    let temp = arr[i];
    let j = i - 1;

    while (j >= left && arr[j] > temp) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = temp;
  }
};

const merge = (arr, left, mid, right) => {
  // 배열을 두 개의 조각으로 분할
  let len1 = mid - left + 1;
  let len2 = right - mid;
  let part1 = Array.from({ length: len1 }, () => 0);
  let part2 = Array.from({ length: len2 }, () => 0);

  for (let x = 0; x < len1; x++) part1[x] = arr[l + x];
  for (let x = 0; x < len2; x++) part2[x] = arr[m + l + x];

  let [i, j, k] = [0, 0, l];
  while (i < len1 && j < len2) {
    arr[k] = left[i] <= right[j] ? left[i++] : right[j++];
  }
  while (i < len1) arr[k++] = left[i++];
  while (j < len2) arr[k++] = right[j++];
};

const timSort = (arr, n) => {
  let minRun = minRunLength(MIN_MERGE);

  for (let i = 0; i < n; i += minRun) {
    insertionSort(arr, i, Math.min(i + MIN_MERGE - 1, n - 1));
  }

  for (let size = minRun; size < n; size *= 2) {
    for (let left = 0; left < n; left += size * 2) {
      let mid = left + size - 1;
      let right = Math.min(left + 2 * size - 1, n - 1);

      if (mid < right) mergeSort(arr, left, mid, right);
    }
  }
};

const arr = [5, 1, 23, 7, 3, 4, 2];

timSort(arr, arr.length);
console.log(arr);

성능 평가 (Big-O)

• [시간 복잡도] 최선: O(N)
• [시간 복잡도] 평균: O(NlogN)
• [시간 복잡도] 최악: O(NlogN)
• [공간 복잡도] 최악: O(N)

Summary 🎉

버블 정렬부터 팀 정렬까지 총 11가지의 정렬 알고리즘을 알아 보았습니다. 본문에서 소개한 알고리즘 외에도 많은 알고리즘이 존재하는데, 실제로 사용하는 알고리즘은 어느 정도 정해져 있습니다. 일반적으로 속도(시간 복잡도)가 빠르면 그것만 쓰면 되지 않냐는 궁금증이 생길 수 있는데, 정렬 알고리즘마다 사용하기 좋은 데이터 집합이 있고, 또한 안정성(참조 지역성)의 문제도 존재합니다. 그렇기에 정렬 알고리즘이 당장 필요하다면, 정렬이 필요한 데이터 집합의 타입이나 사이즈를 보고 잘 고려한 다음 선택해야 합니다.

References 📝

• Tim sort에 대해 알아보자
• GeeksforGeeks (Sort Algorithms)
• 10 Best Sorting Algorithms - Explained with Simple Examples
• What is stability in sorting algorithms and why is it important?