Quick Sort

Q: 퀵 정렬의 시간 복잡도는 어떻게 되나요?

퀵 정렬은 평균 `O(n log n)`이고 최선의 경우에도 `O(n log n)`이지만, 분할이 지속적으로 불균형할 때 최악의 경우 `O(n²)`로 저하됩니다. 무작위 또는 median-of-three 피벗을 쓰면 최악의 경우가 매우 드물어집니다.

Q: 왜 정렬된 배열에서 퀵 정렬이 O(n²)가 되나요?

첫 번째나 마지막 원소 같은 고정 피벗을 쓰면, 이미 정렬된 입력에서는 각 분할이 원소를 하나만 떼어내어 `log n` 대신 `n` 단계의 재귀가 생깁니다. 피벗을 무작위 또는 median-of-three로 고르면 이 패턴이 깨지고 `O(n log n)` 동작이 회복됩니다.

마지막 업데이트 2026년 7월 1일

퀵 정렬은 "피벗"을 중심으로 정렬하는 분할 정복 알고리즘입니다. 피벗 원소를 하나 고른 다음, 더 작은 것은 모두 앞에, 더 큰 것은 모두 뒤에 오도록 배열을 분할합니다. 이로써 피벗은 최종 정렬 위치에 고정됩니다. 그다음 왼쪽과 오른쪽 분할에 대해 재귀합니다. 이 시각화는 마지막 원소를 피벗으로 사용하는 Lomuto 방식을 사용합니다. 재생을 눌러 분할과 피벗 배치를 확인하세요.

퀵 정렬은 좋은 캐시 동작과 제자리 분할 덕분에 실제로 가장 빠른 범용 정렬인 경우가 많으며, 평균은 O(n log n)입니다. 최악의 경우는 O(n²)이며(예: 피벗 선택이 나쁜 이미 정렬된 배열), median-of-three나 무작위화 같은 좋은 피벗 전략으로 이를 피할 수 있습니다.

시간 및 공간 복잡도

경우	복잡도	비고
최선의 경우	O(n log n)	균형 잡힌 분할
평균의 경우	O(n log n)	무작위 순서
최악의 경우	O(n²)	지속적으로 불균형한 피벗
공간	O(log n)	재귀 스택(제자리 분할)
안정성	아니오	분할 시 교환이 같은 원소의 순서를 바꿈

단계별 과정

단계	무슨 일이 일어나는가
1	피벗을 고른다(여기서는 범위의 마지막 원소).
2	분할: 피벗보다 작은 원소를 모두 그 왼쪽으로 옮긴다.
3	피벗을 경계로 교환한다 — 이제 최종 위치에 놓인다.
4	왼쪽 분할에 재귀적으로 퀵 정렬을 적용한다.
5	오른쪽 분할에 재귀적으로 퀵 정렬을 적용한다.

예제 풀이

Lomuto 방식(마지막 원소를 피벗)으로 [5, 2, 4, 1] 정렬하기:

패스	배열	동작
시작	`[5, 2, 4, 1]`	전체 범위를 분할한다. 피벗은 `1`(마지막 원소).
1	`[1, 2, 4, 5]`	`1`보다 작은 것이 없으므로 `1`을 인덱스 `0`으로 교환한다. 피벗 `1`은 이제 확정. `[2, 4, 5]`에 대해 오른쪽으로 재귀.
2	`[1, 2, 4, 5]`	피벗 `5`로 `[2, 4, 5]`를 분할한다. `2`와 `4` 모두 더 작으므로 `5`는 끝에 남아 확정. `[2, 4]`에 대해 왼쪽으로 재귀.
3	`[1, 2, 4, 5]`	피벗 `4`로 `[2, 4]`를 분할한다. `2`가 더 작으므로 `4`는 제자리에 남아 확정. `2`는 원소가 하나뿐이므로 이미 정렬됨.
완료	`[1, 2, 4, 5]`	모든 피벗이 제자리에 고정되어 배열이 정렬됨.

언제 퀵 정렬을 사용하는가

사용해야 할 때	피해야 할 때
상수 계수가 작은 빠르고 범용적인 메모리 내 정렬이 필요할 때.	최악의 경우 `O(n log n)` 시간이 보장되어야 할 때(힙 정렬이나 병합 정렬 사용).
메모리가 빠듯할 때 — 분할이 제자리에서 이루어지며 `O(log n)` 스택만 필요함.	같은 키의 순서를 보존하는 안정 정렬이 필요할 때.
데이터가 무작위이거나 알 수 없는 순서이고 무작위 또는 median-of-three 피벗을 사용할 때.	입력이 이미 정렬되었거나 거의 정렬되었고 피벗이 고정되어 `O(n²)`를 유발할 때.
퀵 정렬은 메모리에 순차적으로 접근하므로 좋은 캐시 지역성이 중요할 때.	연결 리스트를 정렬할 때. 이 경우 병합 정렬이 퀵 정렬이 의존하는 무작위 접근을 피함.

Quick Sort 코드

Python, JavaScript, Java, C++, C로 작성된 깔끔하고 실행 가능한 Quick Sort 구현입니다. 언어를 선택해 코드를 복사하거나 Coddy 플레이그라운드에서 바로 열어보세요.

Python로 구현한 Quick Sort 코드Python
1def quick_sort(a, low=0, high=None):2    if high is None:3        high = len(a) - 14    if low < high:5        p = partition(a, low, high)6        quick_sort(a, low, p - 1)7        quick_sort(a, p + 1, high)8    return a9
10
11def partition(a, low, high):12    # Lomuto partition: everything < pivot moves left of it13    pivot = a[high]14    i = low15    for j in range(low, high):16        if a[j] < pivot:17            a[i], a[j] = a[j], a[i]18            i += 119    a[i], a[high] = a[high], a[i]20    return i21
22
23nums = [10, 7, 8, 9, 1, 5]24print("Before:", nums)25quick_sort(nums)26print("After: ", nums)
이 코드를 Python 플레이그라운드에서 실행하기

JavaScript로 구현한 Quick Sort 코드JavaScript
1function quickSort(a, lo = 0, hi = a.length - 1) {2    if (lo >= hi) return a;3    const p = partition(a, lo, hi);4    quickSort(a, lo, p - 1);5    quickSort(a, p + 1, hi);6    return a;7}8
9// Lomuto partition: last element is the pivot10function partition(a, lo, hi) {11    const pivot = a[hi];12    let i = lo;13    for (let j = lo; j < hi; j++) {14        if (a[j] < pivot) {15            [a[i], a[j]] = [a[j], a[i]];16            i++;17        }18    }19    [a[i], a[hi]] = [a[hi], a[i]];20    return i;21}22
23const data = [5, 2, 9, 1, 7, 3];24console.log("Before:", data);25console.log("Sorted:", quickSort([...data]));
이 코드를 JavaScript 플레이그라운드에서 실행하기

Java로 구현한 Quick Sort 코드Java
1import java.util.Arrays;2
3public class Main {4    static void quickSort(int[] arr, int low, int high) {5        if (low >= high) return;6        int p = partition(arr, low, high);7        quickSort(arr, low, p - 1);8        quickSort(arr, p + 1, high);9    }10
11    // Lomuto partition: last element is the pivot12    static int partition(int[] arr, int low, int high) {13        int pivot = arr[high];14        int i = low - 1;15        for (int j = low; j < high; j++) {16            if (arr[j] < pivot) swap(arr, ++i, j);17        }18        swap(arr, i + 1, high);19        return i + 1;20    }21
22    static void swap(int[] arr, int a, int b) {23        int tmp = arr[a];24        arr[a] = arr[b];25        arr[b] = tmp;26    }27
28    public static void main(String[] args) {29        int[] arr = {10, 7, 8, 9, 1, 5};30        System.out.println("Before: " + Arrays.toString(arr));31        quickSort(arr, 0, arr.length - 1);32        System.out.println("After:  " + Arrays.toString(arr));33    }34}
이 코드를 Java 플레이그라운드에서 실행하기

C++로 구현한 Quick Sort 코드C++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6    for (int x : a) std::cout << x << " ";7    std::cout << "\n";8}9
10// Lomuto partition: place the pivot in its final position11int partition(std::vector<int>& a, int lo, int hi) {12    int pivot = a[hi];13    int i = lo;14    for (int j = lo; j < hi; ++j) {15        if (a[j] < pivot) std::swap(a[i++], a[j]);16    }17    std::swap(a[i], a[hi]);18    return i;19}20
21void quickSort(std::vector<int>& a, int lo, int hi) {22    if (lo >= hi) return;23    int p = partition(a, lo, hi);24    quickSort(a, lo, p - 1);25    quickSort(a, p + 1, hi);26}27
28int main() {29    std::vector<int> data = {10, 7, 8, 9, 1, 5};30    std::cout << "Before: ";31    printVec(data);32    quickSort(data, 0, static_cast<int>(data.size()) - 1);33    std::cout << "After:  ";34    printVec(data);35    return 0;36}
이 코드를 C++ 플레이그라운드에서 실행하기

C로 구현한 Quick Sort 코드C
1#include <stdio.h>2
3void printArr(const int a[], int n) {4    for (int i = 0; i < n; i++) printf("%d ", a[i]);5    printf("\n");6}7
8void swap(int* x, int* y) {9    int tmp = *x;10    *x = *y;11    *y = tmp;12}13
14// Lomuto partition: place the pivot in its final position15int partition(int a[], int lo, int hi) {16    int pivot = a[hi];17    int i = lo;18    for (int j = lo; j < hi; j++) {19        if (a[j] < pivot) swap(&a[i++], &a[j]);20    }21    swap(&a[i], &a[hi]);22    return i;23}24
25void quickSort(int a[], int lo, int hi) {26    if (lo >= hi) return;27    int p = partition(a, lo, hi);28    quickSort(a, lo, p - 1);29    quickSort(a, p + 1, hi);30}31
32int main(void) {33    int data[] = {10, 7, 8, 9, 1, 5};34    int n = sizeof(data) / sizeof(data[0]);35    printf("Before: ");36    printArr(data, n);37    quickSort(data, 0, n - 1);38    printf("After:  ");39    printArr(data, n);40    return 0;41}
이 코드를 C 플레이그라운드에서 실행하기

Quick Sort 자주 묻는 질문

퀵 정렬의 시간 복잡도는 어떻게 되나요?

퀵 정렬은 평균 O(n log n)이고 최선의 경우에도 O(n log n)이지만, 분할이 지속적으로 불균형할 때 최악의 경우 O(n²)로 저하됩니다. 무작위 또는 median-of-three 피벗을 쓰면 최악의 경우가 매우 드물어집니다.

퀵 정렬은 안정 정렬인가요?

아니요. 표준 제자리 분할은 멀리 떨어진 원소를 교환하므로 같은 키의 상대 순서가 바뀔 수 있습니다. 안정 변형이 존재하지만, 퀵 정렬의 제자리 이점을 포기하게 됩니다.

퀵 정렬이 병합 정렬보다 흔히 빠른 이유는 무엇인가요?

퀵 정렬은 뛰어난 캐시 지역성으로 추가 버퍼 없이 제자리에서 분할하므로 상수 계수가 작습니다. 병합 정렬은 같은 O(n log n) 한계를 달성하지만 O(n) 버퍼와 더 많은 데이터 이동 비용을 치릅니다.

퀵 정렬과 병합 정렬 중 무엇을 사용해야 하나요?

메모리 내 배열을 빠르고 제자리에서 정렬한다면 퀵 정렬을 고르세요. 작은 상수 계수 덕분에 대개 우세합니다. 안정 정렬, 보장된 O(n log n) 최악의 경우, 또는 RAM에 들어가지 않는 연결 리스트나 외부 데이터를 정렬해야 한다면 병합 정렬을 고르세요.

왜 정렬된 배열에서 퀵 정렬이 O(n²)가 되나요?

첫 번째나 마지막 원소 같은 고정 피벗을 쓰면, 이미 정렬된 입력에서는 각 분할이 원소를 하나만 떼어내어 log n 대신 n 단계의 재귀가 생깁니다. 피벗을 무작위 또는 median-of-three로 고르면 이 패턴이 깨지고 O(n log n) 동작이 회복됩니다.

Lomuto와 Hoare 분할 방식의 차이는 무엇인가요?

Lomuto 방식은 왼쪽에서 오른쪽으로 훑는 단일 인덱스를 사용하며 코드가 더 단순해 이 시각화에서 사용합니다. Hoare 방식은 안쪽으로 이동하는 두 개의 포인터를 사용하고 보통 교환이 더 적어 실제로 더 빠르지만, 분할 단계에서 피벗을 최종 위치에 놓지는 않습니다.