퀵 정렬 (Quick Sort, 퀵 소트)

TL;DR — 3줄 핵심 요약

• 문제: 퀵 정렬은 평균 O(n log n)으로 빠르지만, 피벗을 잘못 고르면 이미 정렬된 배열에서 O(n²)까지 느려진다.

• 기술/원인: 피벗을 기준으로 작은 값과 큰 값을 나누고, 나뉜 두 구간에 같은 일을 반복한다. 분할이 한쪽으로만 되면 비교 횟수가 (n-1)+(n-2)+…+1이 되어 제곱이 된다.

• 해결/인사이트: 랜덤 피벗, 미디언-오브-쓰리, 작은 구간의 삽입 정렬 전환, 꼬리 재귀, Introsort로 최악을 피한다. C++ std::sort도 Introsort를 쓴다.

들어가며

퀵 정렬(Quick Sort) 알고리즘의 동작 과정을 시각적으로 표현

한 기업의 필기 테스트에서 나온 문제를 계기로 퀵 정렬을 다시 정리했다. 퀵 정렬은 평균 속도가 빠르고 추가 메모리를 거의 쓰지 않아 널리 쓰인다. 이 글은 기본 개념, 동작 원리, 최악의 경우가 생기는 이유, 그리고 그것을 줄이는 방법을 순서대로 다룬다.

퀵 정렬이란

분할 정복 방식의 정렬이다. 배열에서 기준 값을 하나 고르고, 그 값보다 작은 것과 큰 것을 양쪽으로 나눈 뒤, 나뉜 두 구간에 같은 일을 반복한다.

세 단계

1. 피벗 선택: 배열에서 값을 하나 고른다. 보통 첫 값, 마지막 값, 또는 무작위로 고른다.
2. 분할: 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 옮긴다. 이때 피벗은 자기 자리를 찾는다.
3. 재귀: 왼쪽 구간과 오른쪽 구간에 같은 과정을 반복한다. 구간의 길이가 1 이하이면 멈춘다.

특징

• 평균 O(n log n)이다. 실제 데이터에서는 대체로 매우 빠르다.
• 제자리(in-place) 정렬이다. 추가 배열 없이 원본 배열 안에서 값을 바꾼다.
• 불안정 정렬이다. 값이 같은 원소의 원래 순서는 보장하지 않는다.
• 정렬된 배열이나 역순 배열에서 피벗을 한쪽 끝으로 고르면 성능이 크게 떨어진다.

동작 원리

아래 코드는 마지막 값을 피벗으로 쓰는 가장 단순한 형태다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];        // 마지막 값을 피벗으로
    int i = low - 1;              // 작은 값이 놓일 자리의 끝
    for (int j = low; j < high; ++j) {
        if (arr[j] <= pivot) {
            ++i;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);  // 피벗을 자기 자리로
    return i + 1;
}

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

분할이 하는 일

i는 피벗보다 작거나 같은 값이 모인 구간의 마지막 위치다. j가 배열을 한 칸씩 지나가며 피벗보다 작은 값을 만나면 i를 늘리고 두 값을 바꾼다. 반복이 끝나면 i+1이 피벗이 들어갈 자리이고, 그 왼쪽은 모두 피벗 이하, 오른쪽은 모두 피벗 이상이 된다.

재귀의 끝

구간 길이가 1이면 이미 정렬된 상태이므로 아무것도 하지 않는다. 그래서 low < high일 때만 재귀를 부른다. 이 조건이 없으면 무한히 호출된다.

제자리 정렬이란

추가 배열을 만들지 않고 원본 배열 안에서 값을 바꿔 정렬하는 방식이다. 메모리를 적게 쓰고, 값이 연속된 공간에 있어 CPU 캐시를 잘 쓴다. 퀵 정렬은 병합 정렬과 달리 정렬된 두 구간을 합치는 단계가 없다.

시간복잡도

• 평균과 최선: O(n log n). 분할이 절반씩 균형을 이룰 때 단계마다 n번 비교하고 단계 수가 log n이다.
• 최악: O(n²). 피벗이 매번 가장 작거나 큰 값이 되어 한쪽에 n-1, 그다음 n-2개가 남을 때 비교 횟수가 (n-1)+(n-2)+…+1 = n(n-1)/2가 된다.
• 공간: 재귀 호출 스택이 평균 O(log n), 최악 O(n)이다.

최악의 경우는 언제 생기나

이미 오름차순으로 정렬된 배열 [1, 2, 3, 4, 5]에서 마지막 값을 피벗으로 고르면, 첫 분할에서 피벗 5의 왼쪽에 4개가 남고, 다음 분할에서도 왼쪽에 3개가 남는 식으로 한쪽만 줄어든다. 내림차순 배열에서 첫 값을 피벗으로 골라도 같은 일이 생긴다.

정렬이 거의 끝난 데이터를 자주 다루는 프로그램에서는 이 경우가 드물지 않다. 그래서 피벗을 고르는 방법이 성능을 좌우한다.

최악의 경우를 줄이는 방법

1. 무작위 피벗

int randomIndex = low + rand() % (high - low + 1);
swap(arr[randomIndex], arr[high]);

입력 순서에 따른 편향을 없앤다. 이미 정렬된 배열이 들어와도 피벗이 한쪽 끝일 확률이 낮아져 평균적인 성능에 가까워진다.

2. 미디언-오브-쓰리

첫 값, 가운데 값, 마지막 값 중 크기 순서로 중간인 값을 피벗으로 쓴다. 정렬된 배열에서도 가운데 값이 피벗이 되어 분할이 균형을 이룬다.

3. 작은 구간은 삽입 정렬로

구간 길이가 10~16 정도로 작아지면 삽입 정렬로 바꾼다. 작은 배열에서는 재귀 호출 비용이 정렬 자체보다 크기 때문이다.

4. 꼬리 재귀 줄이기

두 구간 중 더 큰 쪽을 재귀로 부르고 작은 쪽은 반복문으로 처리하면 재귀 깊이를 log n 수준으로 묶을 수 있다. 스택 메모리를 아끼고 최악의 경우에도 스택이 넘치지 않게 된다.

5. Introsort

퀵 정렬로 시작하되 재귀 깊이가 log n의 일정 배수를 넘으면 힙 정렬로 바꾼다. 힙 정렬은 최악에도 O(n log n)이므로 전체 성능의 상한이 보장된다. C++ 표준 라이브러리의 std::sort가 이 방식으로 구현되어 있다.

나가며

퀵 정렬은 평균 성능이 좋고 메모리를 적게 쓰지만, 피벗 선택에 따라 성능이 크게 달라진다. 최악의 경우를 이해하고 개선 방법을 함께 알고 있으면, 정렬을 직접 구현하거나 라이브러리 정렬의 동작을 판단할 때 도움이 된다. 다만 코드를 작성한 것과 실제 입력에서 성능이 나오는 것은 다르므로, 정렬된 데이터와 역순 데이터를 넣어 비교 횟수를 세어 보는 확인이 필요하다.

참고 자료

• Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (3rd ed.)
• Musser, D. R., Introsort: a hybrid sorting algorithm, Software: Practice and Experience, 27(8), 1997
• C++ Reference, std::sort

자주 묻는 질문 (FAQ)

Q1. 퀵 정렬이 병합 정렬보다 항상 빠른가요?

A. 아니다. 평균적으로는 퀵 정렬이 빠르고 메모리도 적게 쓴다. 다만 병합 정렬은 항상 O(n log n)이 보장되고 안정 정렬이다. 최악의 경우를 피할 수 없거나 순서를 유지해야 하면 병합 정렬이 낫다.

Q2. 이미 정렬된 배열에서 왜 느려지나요?

A. 마지막 값을 피벗으로 쓰면 이미 정렬된 배열에서는 매번 가장 큰 값이 피벗이 된다. 분할이 한쪽으로만 되어 구간이 1개씩 줄어들고, 비교 횟수가 제곱으로 늘어난다.

Q3. std::sort는 어떤 정렬인가요?

A. Introsort다. 퀵 정렬로 시작하고, 재귀 깊이가 기준을 넘으면 힙 정렬로, 구간이 작으면 삽입 정렬로 바꾼다. 그래서 평균은 빠르고 최악의 성능도 O(n log n)으로 제한된다.