ds · 09

정렬 알고리즘

자료구조정렬알고리즘

정렬(Sort)은 데이터를 특정 순서(오름차순/내림차순)로 재배열하는 연산입니다. 같은 목표를 이루는 방법은 다양하며, 알고리즘마다 시간복잡도·공간복잡도·안정성(stability)에서 뚜렷한 차이를 보입니다. 여기서는 대표적인 비교 기반 정렬인 버블·병합·퀵 정렬을 같은 배열로 비교합니다.

핵심 개념

버블 정렬 (Bubble Sort)

인접한 두 원소를 비교해 순서가 잘못됐으면 교환합니다. 구현이 가장 단순하지만 시간복잡도는 O(n²)로 느립니다. 추가 메모리가 필요 없는 제자리(in-place) 정렬입니다.

핵심 개념

병합 정렬 (Merge Sort)

배열을 절반씩 나눈 뒤, 정렬된 두 부분을 합치는 분할 정복(Divide and Conquer) 알고리즘입니다. 항상 O(n log n)을 보장하지만, 병합 과정에 임시 배열이 필요해 O(n)의 추가 공간을 씁니다.

핵심 개념

퀵 정렬 (Quick Sort)

기준값(pivot)을 정해 작은 값과 큰 값으로 분할(partition)하고 재귀적으로 정렬합니다. 평균 O(n log n)로 실전에서 빠른 편이지만, 피벗이 계속 한쪽으로 치우치면 최악의 경우 O(n²)입니다.

핵심 개념

비교 기반 정렬의 한계

두 원소를 비교해 순서를 정하는 방식의 정렬은 최악의 경우 O(n log n)보다 빠를 수 없다고 알려져 있습니다. 이보다 빠른 정렬이 필요하면 계수 정렬·기수 정렬처럼 비교하지 않는 방식을 사용합니다.

핵심 개념

안정 정렬 (Stable Sort)

값이 같은 원소들의 상대적 순서를 유지하는 정렬을 안정 정렬이라 합니다. 버블·병합 정렬은 안정 정렬이지만, 퀵 정렬(Lomuto 분할)은 일반적으로 안정 정렬이 아닙니다.

핵심 개념

제자리 정렬 (In-place)

입력 크기에 비례하지 않는 추가 메모리만 사용하는 정렬입니다. 버블·퀵 정렬은 추가 배열 없이 제자리에서 정렬하지만(퀵 정렬은 재귀 호출 스택 제외), 병합 정렬은 병합을 위해 O(n) 임시 배열이 필요합니다.

시간복잡도 비교 — 버블 정렬은 평균·최악 모두 O(n²)입니다. 병합 정렬은 최선·평균·최악이 항상 O(n log n)으로 일정합니다. 퀵 정렬은 평균 O(n log n)이지만 피벗 선택이 나쁘면 최악의 경우 O(n²)까지 나빠집니다.

공간복잡도 비교 — 버블·퀵 정렬은 O(1)(퀵 정렬은 재귀 호출 스택으로 평균 O(log n), 파티션이 한쪽으로 치우치면 최악 O(n)) 추가 공간만 필요한 제자리 정렬입니다. 병합 정렬은 병합 단계의 임시 배열 때문에 O(n) 공간이 필요합니다.

실전 선택 기준 — 데이터가 작거나 거의 정렬되어 있으면 단순한 정렬(삽입 정렬 등)도 충분합니다. 안정성과 예측 가능한 성능이 중요하면 병합 정렬을, 평균적인 속도가 가장 중요하면 퀵 정렬을 선택합니다. 많은 표준 라이브러리는 이들을 혼합한 정렬(Timsort, Introsort 등)을 사용합니다.

분할 정복과의 연결 — 병합 정렬과 퀵 정렬은 모두 "나누고(divide) 각각 해결한 뒤(conquer) 합친다"는 분할 정복 패턴을 따릅니다. 이 패턴은 이후 다룰 동적 프로그래밍, 다익스트라 알고리즘 등 다른 알고리즘 설계 기법과도 이어집니다.

정렬을 왜 여러 가지로 배우나

정렬은 가장 오래되고 많이 연구된 문제 중 하나이고, 알고리즘마다 시간, 추가 메모리, 안정성, 입력에 대한 민감도가 다릅니다. 단순한 버블 정렬부터 분할 정복의 병합·퀵 정렬까지 보면 '같은 문제를 푸는 방법이 이렇게 달라질 수 있다'는 감각이 생깁니다. 정렬 알고리즘끼리의 실제 비교 횟수는 정렬 비교 토픽에서 숫자로 봅니다.

숫자로 확인하기

n = 1,000일 때 — n²은 1,000,000이고 n log₂ n은 약 10,000입니다. 약 100배 차이입니다. 버블 정렬은 최악에 n(n − 1) / 2 = 499,500번 비교합니다.

n = 1,000,000일 때 — n²은 10¹²이고 n log₂ n은 약 2×10⁷입니다. 같은 컴퓨터에서 몇 초와 며칠의 차이가 날 수 있는 규모입니다.

계수 정렬 — 0~150 사이의 나이 1,000,000개를 세면, 값의 범위 k = 151에 대해 O(n + k) ≈ 1,000,151번의 작업으로 끝납니다. 비교를 하지 않아서 n log n 하한이 적용되지 않습니다.

피벗이 나쁠 때 — 이미 정렬된 n개에서 항상 끝 값을 피벗으로 쓰는 퀵 정렬은 n²/2 수준입니다. 1,000,000개면 약 5×10¹¹입니다.

자주 하는 오해

O(n log n)이면 다 비슷하다 — 점근 표기는 상수와 메모리 접근 패턴을 버립니다. 같은 O(n log n)이어도 캐시 효율과 비교·이동 횟수가 달라 실제 시간이 다릅니다.

비교 정렬은 O(n log n)보다 빠를 수 없으니 정렬은 그게 한계다 — 원소끼리 비교해서 정렬하는 알고리즘의 최악 하한입니다. 계수 정렬이나 기수 정렬은 비교를 쓰지 않아서 입력 범위 같은 조건이 맞으면 더 빠를 수 있습니다.

안정 정렬은 정렬 결과가 더 정확하다 — 결과의 정확성이 아니라 같은 키를 가진 원소들의 원래 순서를 지켜 주느냐의 차이입니다. 다중 키로 여러 번 정렬할 때 중요합니다.

이미 정렬된 데이터는 어떤 정렬이든 빠르다 — 퀵 정렬은 피벗을 끝 값으로 쓰면 오히려 최악이 되고, 삽입 정렬이나 Timsort 같은 알고리즘은 거의 정렬된 입력에서 빠르게 끝납니다.

면접에서 이렇게 물어요

면접 질문

버블 정렬을 개선할 수 있나요?

한 번의 패스에서 교환이 한 번도 없었다면 이미 정렬된 것이므로 그 시점에 멈춥니다. 이 개선을 넣으면 이미 정렬된 입력에서는 O(n)에 끝나지만(개선이 없는 기본형은 정렬된 입력에서도 O(n²)), 평균과 최악은 여전히 O(n²)입니다.

면접 질문

계수 정렬은 언제 쓰나요?

정수처럼 값의 범위 k가 n에 비해 크지 않을 때 O(n + k)에 정렬할 수 있습니다. 범위가 크면 카운트 배열의 메모리와 시간이 커져서 맞지 않습니다.

면접 질문

안정 정렬이 필요한 예를 들어 보세요.

이름순으로 정렬된 목록을 학년으로 다시 정렬할 때 같은 학년 안에서 이름순을 유지하려면 안정 정렬이어야 합니다.

면접 질문

실무에서는 어떤 정렬을 쓰나요?

여러 알고리즘을 섞은 정렬을 씁니다. 파이썬은 Timsort를 쓰고, 작은 구간은 이진 삽입 정렬로 처리한다고 CPython 문서에 설명되어 있습니다.

실제 시스템에서는

Python — 문서는 sorted()와 list.sort()가 안정 정렬이 보장되고 Timsort를 쓴다고 설명합니다. CPython 구현 노트는 작은 구간을 이진 삽입 정렬로 늘려 병합한다고 설명합니다.

Java — Java 21 문서 기준으로 Arrays.sort는 기본형 배열에 Dual-Pivot Quicksort, 객체 배열에 안정적인 TimSort 계열 병합 정렬을 쓴다고 문서가 설명합니다.

데이터베이스 — ORDER BY가 인덱스 순서를 그대로 쓰지 못하면 정렬 작업이 필요합니다. 쿼리 실행 계획에서 정렬 노드를 볼 수 있습니다. 자세한 내용은 쿼리 실행 계획 토픽에서 봅니다.

함께 보면 좋은 토픽

정렬 비교 — 병합·퀵·힙 정렬의 비교 횟수를 숫자로 비교합니다.

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

이진 탐색 — 정렬된 데이터에서 찾는 방법을 봅니다.

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

투 포인터 / 슬라이딩 윈도우 — 정렬한 뒤 쓰는 대표 기법을 봅니다.

참고 자료

Python 정렬 — Sorting Techniques — Python documentation

CPython listsort — listsort.txt — CPython source (Tim Peters)

Java Arrays — Arrays — Java SE 21 API

교재 — Cormen, Leiserson, Rivest, Stein, "Introduction to Algorithms" 4판, "Sorting in Linear Time" 장(비교 정렬의 하한, 계수 정렬)

Java — 버블 정렬 (Bubble Sort)

/* ── 버블 정렬: 인접한 두 원소를 비교해 큰 값을 뒤로 보냄 ─── */
public void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                swapped = true;
            }
        }
        // 이번 패스에서 교환이 없었다면 이미 정렬 완료 → 조기 종료
        if (!swapped) break;
    }
}

매 패스마다 가장 큰 값이 "거품처럼" 맨 뒤로 떠오른다고 해서 버블 정렬이라 부릅니다.
swapped 플래그로 조기 종료를 구현하면 최선의 경우(이미 정렬된 배열) O(n)까지 빨라지지만, 평균·최악은 O(n²)입니다.
추가 배열 없이 원본 배열 안에서 교환만 하므로 공간복잡도는 O(1)입니다.

Java — 병합 정렬 (Merge Sort)

/* ── 병합 정렬: 절반으로 분할 후, 정렬된 두 부분을 병합 ──── */
public void mergeSort(int[] arr, int lo, int hi) {
    if (lo >= hi) return;              // 원소가 1개면 이미 정렬된 상태

    int mid = (lo + hi) / 2;
    mergeSort(arr, lo, mid);          // 왼쪽 절반 정렬
    mergeSort(arr, mid + 1, hi);     // 오른쪽 절반 정렬
    merge(arr, lo, mid, hi);         // 정렬된 두 부분을 병합
}

private void merge(int[] arr, int lo, int mid, int hi) {
    int[] left  = Arrays.copyOfRange(arr, lo, mid + 1);
    int[] right = Arrays.copyOfRange(arr, mid + 1, hi + 1);
    int i = 0, j = 0, k = lo;

    while (i < left.length && j < right.length) {
        arr[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
    }
    while (i < left.length)  arr[k++] = left[i++];   // 왼쪽 나머지 복사
    while (j < right.length) arr[k++] = right[j++];  // 오른쪽 나머지 복사
}

left[i] <= right[j] 조건(왼쪽을 우선)이 같은 값의 상대적 순서를 유지시켜 병합 정렬을 안정 정렬로 만듭니다.
분할은 항상 정확히 절반씩 이루어지므로 재귀 깊이가 O(log n)이고, 각 깊이에서 병합에 O(n)이 들어 전체 시간복잡도는 최선·평균·최악 모두 O(n log n)입니다.
단, left·right 임시 배열 때문에 공간복잡도는 O(n)입니다.

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

/* ── 퀵 정렬: 피벗 기준으로 분할 후 각 부분을 재귀 정렬 ──── */
public void quickSort(int[] arr, int lo, int hi) {
    if (lo >= hi) return;

    int pivotIdx = partition(arr, lo, hi);
    quickSort(arr, lo, pivotIdx - 1);   // 피벗보다 작은 쪽
    quickSort(arr, pivotIdx + 1, hi);  // 피벗보다 큰 쪽
}

/* ── Lomuto 파티션: 마지막 원소를 피벗으로 사용 ──────────── */
private int partition(int[] arr, int lo, int hi) {
    int pivot = arr[hi];
    int i = lo - 1;               // "피벗보다 작은 영역"의 마지막 인덱스

    for (int j = lo; j < hi; j++) {
        if (arr[j] < pivot) {
            i++;
            int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
        }
    }
    int tmp = arr[i + 1]; arr[i + 1] = arr[hi]; arr[hi] = tmp;  // 피벗을 경계로 이동
    return i + 1;                // 피벗의 최종 위치
}

파티션이 끝나면 피벗은 항상 최종 위치에 놓이고, 왼쪽은 모두 피벗보다 작은 값·오른쪽은 모두 큰 값이 됩니다 — 그래서 피벗은 이후 재귀 호출에서 제외됩니다.
평균적으로 피벗이 배열을 절반씩 나누면 O(n log n)이지만, 이미 정렬된 배열에서 마지막 원소를 피벗으로 고르면 매번 한쪽에 n-1개가 몰려 최악의 경우 O(n²)이 됩니다.
실전 라이브러리는 이를 피하기 위해 피벗을 무작위로 고르거나 세 값의 중앙값을 사용합니다.

버블 정렬(Bubble Sort)의 평균/최악 시간 복잡도는?

인접한 두 원소를 계속 비교/교환하며 전체를 여러 번 훑습니다.

버블 정렬은 인접 원소를 비교하며 큰 값을 뒤로 보내는 과정을 n번 반복해 평균/최악 시간 복잡도가 O(n^2)입니다.

병합 정렬(Merge Sort)이 O(n log n)을 보장하는 이유는?

분할 정복(Divide and Conquer) 방식입니다.

병합 정렬은 배열을 절반씩 나누는 데 log n단계가 걸리고, 각 단계마다 병합에 O(n)이 걸려 전체 O(n log n)을 보장합니다. 최악의 경우에도 성능이 일정합니다.

퀵 정렬(Quick Sort)의 최악 시간 복잡도가 O(n^2)이 되는 경우는?

분할이 균등하지 않으면 재귀 깊이가 깊어집니다.

퀵 정렬은 피벗을 기준으로 분할하는데, 피벗이 계속 최솟값/최댓값으로 뽑혀 한쪽 파티션에 거의 모든 원소가 몰리면 최악의 경우 O(n^2)까지 나빠질 수 있습니다.