algo · 03

정렬 비교

알고리즘정렬Merge Sort

자료구조 토픽(ds-09)에서는 정렬 과정 자체를 막대그래프 애니메이션으로 살펴봤다면, 여기서는 병합 정렬 · 퀵 정렬 · 힙 정렬이 같은 배열을 정렬하는 데 실제로 몇 번 비교하는지를 숫자로 직접 비교합니다. 세 알고리즘 모두 평균적으로 O(n log n)이지만, 구체적인 비교 횟수와 동작 방식은 서로 다릅니다.

핵심 개념

병합 정렬 — 분할 정복

배열을 절반으로 계속 나눈 뒤(분할), 정렬된 두 부분을 다시 합칩니다(병합). 항상 절반씩 나누기 때문에 최선·평균·최악 모두 O(n log n)으로 일정합니다.

핵심 개념

퀵 정렬 — 피벗 기준 분할

기준값(피벗)을 하나 정해 그보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 나눕니다. 평균 O(n log n)이지만, 피벗이 계속 한쪽으로 치우치면 최악의 경우 O(n²)까지 느려질 수 있습니다.

핵심 개념

힙 정렬 — 힙 자료구조 활용

배열을 최대 힙(ds-06 힙 참고)으로 만든 뒤, 가장 큰 값을 하나씩 꺼내 정렬 영역으로 옮깁니다. 최악의 경우에도 O(n log n)입니다.

핵심 개념

비교 횟수는 왜 다른가

같은 O(n log n)이라도 상수 배와 실제 비교 횟수는 알고리즘 구현 방식, 데이터 배치, 피벗 선택 방법에 따라 달라집니다. 이 토픽에서는 원소 8개짜리 동일한 배열에 대해 세 알고리즘의 실제 비교 횟수를 직접 셉니다.

핵심 개념

제자리 정렬 여부

퀵 정렬과 힙 정렬은 추가 배열 없이 원본 배열 안에서 교환만으로 정렬하는 제자리(in-place) 정렬입니다. 병합 정렬은 병합 과정에서 임시 배열이 필요해 추가 공간 O(n)이 듭니다.

핵심 개념

안정 정렬 여부

일반적인 병합 정렬은 같은 값의 상대적 순서를 유지하는 안정 정렬입니다. 일반적인 퀵 정렬과 힙 정렬은 교환 과정에서 같은 값의 순서가 바뀔 수 있는 불안정 정렬입니다.

왜 세 알고리즘 모두 배워야 하나 — 이론적 시간복잡도가 같아도 상황에 따라 유리한 알고리즘이 다릅니다. 같은 값의 순서를 지켜야 하면 병합 정렬, 추가 메모리를 아끼려면 퀵/힙 정렬처럼 상황에 맞는 선택이 필요합니다.

퀵 정렬의 함정 — 이 시각화는 배열이 무작위에 가까워 평균 성능을 보여주지만, 이미 정렬된 배열에 항상 마지막 값을 피벗으로 고르면 매번 한쪽으로만 치우쳐 O(n²)이 됩니다. 그래서 피벗을 무작위로 고르거나 세 값의 중간값을 사용하는 방법이 있습니다.

힙 정렬과 힙 자료구조 — ds-06에서 배운 "삽입할 때마다 힙을 유지하는" 방식과 달리, 힙 정렬은 배열 전체를 한 번에 힙으로 만드는 것부터 시작합니다(build-heap이 O(n)).

이 시각화에서 확인할 것 — 병합·퀵·힙 정렬 탭을 각각 재생해 같은 배열이 다른 경로로 정렬되는 과정을 보고, 마지막 힙 정렬 탭 하단에서 세 알고리즘의 실제 비교 횟수를 막대그래프로 비교하세요.

세 정렬의 유래

퀵 정렬은 토니 호어(C. A. R. Hoare)가 만들어 1961년 CACM의 알고리즘 64(Quicksort)로 발표한 것으로 알려져 있고, 힙 정렬은 1964년 J. W. J. 윌리엄스(Williams)가 CACM에 발표한 알고리즘 232(Heapsort)로 알려져 있습니다. 병합 정렬은 1945년 폰 노이만이 쓴 프로그램이 가장 오래된 사례로 알려져 있습니다. 모두 입력의 원소끼리 비교하는 정렬이라서 최악의 경우 O(n log n)보다 적은 비교로는 정렬할 수 없다는 하한(Ω(n log n))이 같이 적용됩니다.

숫자로 확인하기

원소 8개의 비교 횟수 — 이 시각화의 같은 배열에서 병합 정렬은 16번, 퀵 정렬은 18번, 힙 정렬은 22번 비교합니다. 이 값은 배열 하나에 대한 실측이고, 입력이 달라지면 달라집니다.

비교 정렬의 하한과 견주기 — 원소 8개를 비교로 구분하려면 가능한 순서가 8! = 40,320가지이므로 최악의 경우 최소 ⌈log₂ 40,320⌉ = 16번의 비교가 필요합니다. 이 하한은 모든 입력 중 최악을 기준으로 한 값이라 한 배열의 결과와 직접 비교할 수는 없습니다.

n = 1,000,000일 때 — n log₂ n은 약 2천만, n²은 1조입니다. 퀵 정렬이 평균적으로 n log n 근처로 동작하더라도 피벗이 계속 나쁘면 n² 쪽으로 가는 차이가 이 크기에서 극명합니다.

자주 하는 오해

퀵 정렬이 항상 가장 빠르다 — 평균적으로 빠르지만 피벗 선택이 나쁘면 최악 O(n²)이 되고, 안정 정렬도 아닙니다. 라이브러리는 용도에 따라 다른 정렬을 고릅니다.

O(n log n)끼리는 속도가 같다 — 점근 표기는 상수와 낮은 차수 항을 버립니다. 비교와 이동의 횟수, 메모리 접근 패턴이 달라 실제 시간은 구현마다 다릅니다.

표준 라이브러리 정렬은 퀵 정렬이다 — 자바 문서에서 기본형 배열 정렬은 듀얼 피벗 퀵 정렬이지만 객체 배열 정렬은 안정적인 병합 계열(TimSort)입니다. 파이썬의 list.sort도 안정 정렬(Timsort)입니다.

힙 정렬은 안정 정렬이다 — 힙에서 값을 교환하는 과정에서 같은 값의 순서가 바뀔 수 있어 일반적인 구현은 안정 정렬이 아닙니다.

면접에서 이렇게 물어요

면접 질문

안정 정렬이 왜 필요한가요?

같은 키를 가진 원소의 원래 순서를 유지해야 하는 경우에 필요합니다. 예를 들어 이름순으로 정렬한 목록을 학년으로 다시 정렬할 때 안정 정렬이면 같은 학년 안에서 이름순이 유지됩니다.

면접 질문

퀵 정렬의 최악을 피하는 방법은 무엇인가요?

피벗을 무작위로 고르거나 첫·중간·끝 세 값의 중간값으로 고르면 정렬된 입력에서의 최악을 피할 수 있습니다. 이미 정렬된 입력에 항상 끝 값을 피벗으로 쓰는 구현이 최악의 전형입니다. 다만 중간값 방식만으로 최악 O(n²)이 없어지는 것은 아닙니다.

면접 질문

병합 정렬과 힙 정렬 중 언제 무엇을 쓰나요?

병합 정렬은 안정적이고 항상 O(n log n)이지만 임시 공간 O(n)이 듭니다. 힙 정렬은 제자리로 최악에도 O(n log n)이지만 안정 정렬이 아니고 메모리 접근이 흩어집니다.

면접 질문

비교 정렬은 O(n log n)보다 빨라질 수 없나요?

원소끼리 비교만으로 정렬하는 알고리즘은 최악의 경우 Ω(n log n)이 필요합니다. 계수 정렬처럼 비교를 쓰지 않는 정렬은 입력의 범위 같은 조건이 있으면 이보다 빠를 수 있습니다.

실제 시스템에서는

Java — Arrays.sort는 기본형 배열에는 듀얼 피벗 퀵 정렬을, 객체 배열에는 안정적인 병합 계열 정렬을 씁니다. 안정성이 필요한 객체 정렬에 이 차이가 의미를 가집니다.

Python — sorted()와 list.sort()는 안정 정렬이 보장됩니다. 여러 번 정렬해 다중 키 정렬을 만들 수 있습니다.

C++ — C++11 이후 표준은 std::sort가 최악에도 O(N log N)번의 비교를 하도록 요구하고, 안정 정렬이 필요하면 std::stable_sort를 씁니다.

함께 보면 좋은 토픽

정렬 알고리즘 — 정렬 과정을 막대그래프 애니메이션으로 봅니다.

힙 — 힙 정렬의 바탕이 되는 힙 자료구조를 봅니다.

시간·공간 복잡도 — O(n log n)과 O(n²)의 차이를 숫자로 봅니다.

이진 탐색 — 정렬된 데이터를 빠르게 찾는 방법을 봅니다.

참고 자료

Java Arrays — Arrays — Java SE 21 API

Python 정렬 — Sorting Techniques — Python documentation

원 논문 — Hoare, "Algorithm 64: Quicksort", Communications of the ACM, 1961

원 논문 — Williams, "Algorithm 232: Heapsort", Communications of the ACM, 1964

교재 — Cormen, Leiserson, Rivest, Stein, "Introduction to Algorithms" 4판, "Heapsort", "Quicksort", "Sorting in Linear Time" 장

Java — 병합 정렬 (Merge Sort)

/* ── 절반으로 나누고, 정렬된 두 절반을 다시 합침 ───────────── */
public void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return;              // 기저 사례: 원소 1개는 이미 정렬됨

    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);            // 왼쪽 절반 정렬
    mergeSort(arr, mid + 1, right);       // 오른쪽 절반 정렬
    merge(arr, left, mid, right);        // 정렬된 두 절반을 합침
}

배열을 계속 절반으로 나누면 깊이는 log₂n, 각 깊이에서 merge가 전체 원소를 한 번씩 비교·복사하므로 O(n)입니다.
깊이(log n) × 각 단계 작업량(n) = O(n log n)이며, 항상 정확히 절반씩 나누기 때문에 입력에 상관없이 이 시간이 보장됩니다.

Java — 퀵 정렬 (Quick Sort, Lomuto 파티션)

/* ── 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 모음 ──────── */
public void quickSort(int[] arr, int lo, int hi) {
    if (lo >= hi) return;

    int pivot = arr[hi];                  // 구간의 마지막 값을 피벗으로 사용
    int i = lo - 1;
    for (int j = lo; j < hi; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr, i, j);              // 피벗보다 작은 값을 앞쪽으로 이동
        }
    }
    swap(arr, i + 1, hi);              // 피벗을 최종 위치로 이동

    int p = i + 1;
    quickSort(arr, lo, p - 1);
    quickSort(arr, p + 1, hi);
}

피벗이 매번 배열을 절반에 가깝게 나누면 병합 정렬처럼 O(n log n)이지만, arr[j] < pivot 비교 결과에 따라 분할 비율이 달라지는 것이 병합 정렬과의 차이입니다.
평균적으로는 O(n log n)이지만, 이미 정렬된 배열에서 항상 마지막 값을 피벗으로 고르면 매번 원소 1개씩만 떼어내는 최악의 경우 O(n²)가 될 수 있습니다.

Java — 힙 정렬 (Heap Sort)

/* ── 최대 힙을 만든 뒤, 루트(최댓값)를 하나씩 꺼내 정렬 ────── */
public void heapSort(int[] arr) {
    int n = arr.length;
    for (int i = n / 2 - 1; i >= 0; i--) {
        siftDown(arr, i, n);             // 배열 전체를 최대 힙으로 구성 — O(n)
    }
    for (int end = n - 1; end > 0; end--) {
        swap(arr, 0, end);              // 루트(최댓값)를 정렬 영역 맨 앞으로
        siftDown(arr, 0, end);         // 줄어든 힙을 다시 정리
    }
}

siftDown 한 번은 힙의 높이(log n)만큼만 비교하면 되므로, n개를 하나씩 꺼내며 매번 siftDown을 호출해도 전체는 O(n log n)입니다.
병합 정렬처럼 최선·평균·최악이 모두 O(n log n)으로 안정적이면서도, 퀵 정렬처럼 추가 배열 없이 원본 배열 안에서 정렬을 끝내는 제자리 정렬이라는 점이 특징입니다.

병합 정렬, 퀵 정렬, 힙 정렬의 평균 시간 복잡도는 공통적으로?

세 알고리즘 모두 효율적인 비교 기반 정렬입니다.

병합 정렬, 퀵 정렬, 힙 정렬은 모두 평균적으로 O(n log n) 시간에 정렬을 완료하는 효율적인 알고리즘입니다.

같은 O(n log n)이어도 정렬 알고리즘마다 실제 비교 횟수가 다를 수 있는 이유는?

Big-O는 '추세'를 나타낼 뿐 정확한 상수는 무시합니다.

Big-O 표기법은 상수 배율이나 세부 구현 차이를 무시한 점근적 추세이므로, 같은 O(n log n)이라도 실제 비교 횟수는 알고리즘 구현에 따라 다를 수 있습니다.

퀵 정렬이 평균적으로 빠르지만 최악의 경우 O(n^2)이 될 수 있는 이유는?

분할이 균등하지 않으면 재귀 깊이와 비교 횟수가 늘어납니다.

퀵 정렬은 피벗을 기준으로 분할하는데, 피벗이 계속 극단값으로 뽑히면 분할이 거의 되지 않아 최악의 경우 O(n^2)까지 나빠질 수 있습니다.