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
이전그래프와 탐색