Ray Book
자료구조와 알고리즘

정렬 알고리즘 비교

버블, 삽입, 병합, 퀵 정렬의 동작 원리와 성능 차이를 시각화합니다

csalgorithmsortingbubble-sortmerge-sortquick-sort

왜 정렬인가

정렬은 컴퓨터 과학에서 가장 많이 연구된 문제 중 하나입니다. 정렬이 중요한 이유는 간단합니다. 정렬된 데이터에서는 검색이 빠릅니다.

100만 개의 데이터에서 특정 값을 찾는다고 합시다. 정렬되지 않은 배열에서는 처음부터 하나씩 확인해야 하므로 최악의 경우 O(n) = 100만 번의 비교가 필요합니다. 하지만 정렬된 배열에서 이진 탐색을 사용하면 O(log n) = 약 20번의 비교로 찾을 수 있습니다.

데이터베이스의 인덱스, 검색 엔진의 역색인, 파일 시스템의 디렉토리 목록 등 정렬은 거의 모든 시스템의 기반입니다.

O(n\u00B2) 정렬

가장 직관적이지만 느린 정렬 알고리즘들입니다. 이해하기 쉽고 구현이 간단하지만, 데이터가 많아지면 사용하기 어렵습니다.

버블 정렬 (Bubble Sort)

인접한 두 원소를 비교하여, 순서가 잘못되었으면 교환합니다. 한 번의 패스가 끝나면 가장 큰 원소가 배열 끝으로 "거품"처럼 올라갑니다.

BUBBLE-SORT(A):
    n = A.length
    for i = 0 to n-2:
        for j = 0 to n-2-i:
            if A[j] > A[j+1]:
                swap(A[j], A[j+1])
function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let swapped = false;
    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
    // 한 번의 패스에서 교환이 없으면 이미 정렬된 것
    if (!swapped) break;
  }
  return arr;
}

선택 정렬 (Selection Sort)

매번 미정렬 부분에서 최솟값을 찾아 맨 앞과 교환합니다.

SELECTION-SORT(A):
    n = A.length
    for i = 0 to n-2:
        minIdx = i
        for j = i+1 to n-1:
            if A[j] < A[minIdx]:
                minIdx = j
        swap(A[i], A[minIdx])
function selectionSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIdx]) {
        minIdx = j;
      }
    }
    if (minIdx !== i) {
      [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
    }
  }
  return arr;
}

삽입 정렬 (Insertion Sort)

카드 게임에서 손에 든 카드를 정렬하는 방식과 같습니다. 새 원소를 이미 정렬된 부분의 올바른 위치에 삽입합니다.

INSERTION-SORT(A):
    for i = 1 to A.length - 1:
        key = A[i]
        j = i - 1
        while j >= 0 and A[j] > key:
            A[j+1] = A[j]      // 오른쪽으로 밀기
            j = j - 1
        A[j+1] = key
function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j]; // 오른쪽으로 한 칸 밀기
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}

삽입 정렬은 거의 정렬된 데이터에서 O(n)에 가까운 성능을 보입니다. 이 특성이 나중에 TimSort에서 활용됩니다.

버블 정렬 시각화

인접한 두 원소를 비교하고 교환하는 과정을 단계별로 확인하세요. 비교 횟수에 주목합니다.

초기 상태1 / 36
비교 횟수:0
비교 중교환정렬 완료
8개의 숫자를 버블 정렬합니다. 인접한 두 원소를 비교하여 순서가 잘못되었으면 교환합니다. 배열 끝에서부터 큰 값이 확정됩니다.

O(n log n) 정렬

분할 정복 (Divide and Conquer) 전략을 사용하는 효율적인 정렬 알고리즘입니다.

병합 정렬 (Merge Sort)

배열을 반으로 나누고, 각 절반을 재귀적으로 정렬한 뒤, 두 정렬된 배열을 병합합니다.

MERGE-SORT(A, left, right):
    if left >= right: return
    mid = (left + right) / 2
    MERGE-SORT(A, left, mid)       // 왼쪽 절반 정렬
    MERGE-SORT(A, mid+1, right)    // 오른쪽 절반 정렬
    MERGE(A, left, mid, right)     // 병합

MERGE(A, left, mid, right):
    L = A[left..mid]
    R = A[mid+1..right]
    i = 0, j = 0, k = left
    while i < L.length and j < R.length:
        if L[i] <= R[j]:
            A[k] = L[i]; i++
        else:
            A[k] = R[j]; j++
        k++
    // 나머지 복사
function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0;
  let j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

  return [...result, ...left.slice(i), ...right.slice(j)];
}

퀵 정렬 (Quick Sort)

피벗 원소를 기준으로 작은 값과 큰 값을 분할하고, 각 부분을 재귀적으로 정렬합니다.

QUICK-SORT(A, low, high):
    if low >= high: return
    pivotIdx = PARTITION(A, low, high)
    QUICK-SORT(A, low, pivotIdx - 1)
    QUICK-SORT(A, pivotIdx + 1, high)

PARTITION(A, low, high):
    pivot = A[high]          // 마지막 원소를 피벗으로
    i = low - 1
    for j = low to high - 1:
        if A[j] <= pivot:
            i++
            swap(A[i], A[j])
    swap(A[i+1], A[high])
    return i + 1
function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low >= high) return arr;

  const pivotIdx = partition(arr, low, high);
  quickSort(arr, low, pivotIdx - 1);
  quickSort(arr, pivotIdx + 1, high);

  return arr;
}

function partition(arr, low, high) {
  const pivot = arr[high];
  let i = low - 1;

  for (let j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }

  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

병합 정렬 시각화

배열을 반으로 나누고 다시 병합하는 과정을 확인하세요. 버블 정렬과 비교 횟수 차이에 주목합니다.

초기 상태1 / 11
비교 횟수:0
비교 중교환정렬 완료병합 중
같은 배열을 병합 정렬합니다. 배열을 반으로 나눈 뒤, 각 부분을 정렬하고 병합합니다. 분할 정복 (Divide and Conquer) 전략입니다.

퀵 정렬 시각화

피벗을 기준으로 분할하고 재귀적으로 정렬하는 과정입니다. 피벗이 제 위치에 확정되는 과정에 주목하세요.

초기 상태1 / 9
비교 횟수:0
비교 중교환정렬 완료피벗분할 영역
같은 배열을 퀵 정렬합니다. 피벗을 선택하고, 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할합니다.

비교 표

알고리즘최선평균최악공간안정성
버블 정렬O(n)O(n\u00B2)O(n\u00B2)O(1)안정
선택 정렬O(n\u00B2)O(n\u00B2)O(n\u00B2)O(1)불안정
삽입 정렬O(n)O(n\u00B2)O(n\u00B2)O(1)안정
병합 정렬O(n log n)O(n log n)O(n log n)O(n)안정
퀵 정렬O(n log n)O(n log n)O(n\u00B2)O(log n) ~ O(n)불안정

버블 정렬과 삽입 정렬의 최선 O(n)은 이미 정렬된 배열에서 달성됩니다. 퀵 정렬의 최악 O(n\u00B2)은 매번 피벗이 최솟값이나 최댓값일 때 발생하며, 이때 재귀 깊이도 O(n)이 되어 공간 복잡도도 O(n)까지 증가합니다.

안정 정렬 vs 불안정 정렬

**안정 정렬 (Stable Sort)**은 같은 키 값을 가진 원소의 상대적 순서를 유지합니다.

예를 들어, 학생 목록을 점수로 정렬할 때:

정렬 전: [{이름: "Alice", 점수: 90}, {이름: "Bob", 점수: 90}, {이름: "Carol", 점수: 85}]

안정 정렬: Carol(85), Alice(90), Bob(90)   -- Alice가 Bob보다 앞 (원래 순서 유지)
불안정 정렬: Carol(85), Bob(90), Alice(90)  -- 순서가 바뀔 수 있음

이것이 중요한 이유는 다중 키 정렬 때문입니다. 먼저 이름순으로 정렬한 뒤, 점수순으로 다시 정렬하면 안정 정렬에서는 같은 점수 내에서 이름순이 유지됩니다. 불안정 정렬에서는 이 순서가 깨집니다.

  • 안정 : 버블, 삽입, 병합 정렬
  • 불안정 : 선택, 퀵 정렬 (퀵 정렬은 분할 과정에서 원소의 상대 순서가 바뀔 수 있습니다)

실무 연결

Array.prototype.sort()와 TimSort

JavaScript의 Array.prototype.sort()는 엔진마다 다른 알고리즘을 사용합니다. V8 엔진 (Chrome, Node.js)은 TimSort를 사용합니다.

TimSort는 병합 정렬과 삽입 정렬의 하이브리드입니다.

  1. 배열에서 이미 정렬된 구간 (run)을 찾습니다
  2. run의 길이가 최소 크기 (minrun, 보통 32~64)보다 짧으면 삽입 정렬로 확장합니다
  3. 인접한 run들을 병합 정렬의 merge로 합칩니다
// V8의 sort()는 안정 정렬 (ES2019 명세)
const students = [
  { name: "Alice", score: 90 },
  { name: "Bob", score: 90 },
  { name: "Carol", score: 85 },
];

students.sort((a, b) => a.score - b.score);
// Carol(85), Alice(90), Bob(90), 안정 정렬이므로 Alice가 Bob 앞

TimSort가 효율적인 이유:

  • 실제 데이터는 완전히 랜덤하지 않습니다. 부분적으로 정렬된 구간이 있는 경우가 많습니다
  • 이미 정렬된 구간을 활용하므로, 거의 정렬된 데이터에서 O(n)에 가깝습니다
  • 최악의 경우에도 O(n log n)을 보장합니다 (퀵 정렬의 O(n\u00B2) 최악 케이스가 없습니다)
  • 안정 정렬입니다

참고 : sort()에 비교 함수를 전달하지 않으면 원소를 문자열로 변환한 뒤 유니코드 순서로 정렬합니다. [10, 9, 2].sort()의 결과는 [10, 2, 9]입니다. 숫자 정렬에는 반드시 (a, b) => a - b를 전달하세요.

V8의 정렬 최적화

V8은 배열의 크기와 타입에 따라 전략을 달리합니다.

  • 짧은 구간 (minrun 미만, 보통 32~64개): 삽입 정렬. TimSort는 짧은 run에 삽입 정렬을 사용합니다
  • 타입이 균일한 배열 (예: 정수만): 더 효율적인 비교 연산을 사용합니다
  • 희소 배열 (빈 슬롯이 있는 배열): 먼저 빈 슬롯을 처리한 후 정렬합니다

시리즈 마무리

6편에 걸쳐 자료구조와 알고리즘의 핵심을 다뤘습니다.

  1. 배열과 링크드 리스트, 연속 메모리 vs 포인터 연결, Big-O 표기법
  2. 스택과 큐, LIFO vs FIFO, 콜 스택과 이벤트 큐
  3. 해시맵, 해시 함수, 충돌 해결, O(1) 조회
  4. 트리와 BST, 계층 구조, 이진 탐색 트리, O(log n) 연산
  5. 그래프와 탐색, 네트워크 구조, BFS, DFS
  6. 정렬 알고리즘, O(n\u00B2) vs O(n log n), 안정성, TimSort

이 시리즈의 핵심 교훈은 자료구조 선택이 곧 성능이라는 것입니다. 같은 문제라도 배열, 해시맵, 트리 중 어떤 것을 선택하느냐에 따라 O(n)이 O(1)이 되거나, O(n\u00B2)이 O(n log n)이 됩니다. 시간 복잡도를 이해하면 "왜 느린지"가 아니라 "어떤 자료구조를 선택해야 하는지"를 판단할 수 있습니다.

자료구조와 알고리즘6 / 6
이전그래프와 탐색