Quick Sort
마지막 업데이트
퀵 정렬은 "피벗"을 중심으로 정렬하는 분할 정복 알고리즘입니다. 피벗 원소를 하나 고른 다음, 더 작은 것은 모두 앞에, 더 큰 것은 모두 뒤에 오도록 배열을 분할합니다. 이로써 피벗은 최종 정렬 위치에 고정됩니다. 그다음 왼쪽과 오른쪽 분할에 대해 재귀합니다. 이 시각화는 마지막 원소를 피벗으로 사용하는 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, Pseudocode로 작성된 깔끔하고 실행 가능한 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)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]));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}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로 구현한 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}Pseudocode로 구현한 Quick Sort 코드
Pseudocode
1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74nums[1] ← 75nums[2] ← 36nums[3] ← 97nums[4] ← 18nums[5] ← 59nums[6] ← 810nums[7] ← 211DECLARE i : INTEGER12
13FUNCTION partition(lo : INTEGER, hi : INTEGER) RETURNS INTEGER14 DECLARE pivot : INTEGER15 DECLARE a : INTEGER16 DECLARE b : INTEGER17 DECLARE temp : INTEGER18 pivot ← nums[hi]19 a ← lo - 120 FOR b ← lo TO hi - 121 IF nums[b] <= pivot THEN22 a ← a + 123 temp ← nums[a]24 nums[a] ← nums[b]25 nums[b] ← temp26 ENDIF27 NEXT b28 temp ← nums[a + 1]29 nums[a + 1] ← nums[hi]30 nums[hi] ← temp31 RETURN a + 132ENDFUNCTION33
34PROCEDURE quickSort(lo : INTEGER, hi : INTEGER)35 DECLARE p : INTEGER36 IF lo < hi THEN37 // Place the pivot, then sort each side of it38 p ← partition(lo, hi)39 CALL quickSort(lo, p - 1)40 CALL quickSort(p + 1, hi)41 ENDIF42ENDPROCEDURE43
44CALL quickSort(1, n)45
46FOR i ← 1 TO n47 OUTPUT nums[i]48NEXT iQuick 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 방식은 안쪽으로 이동하는 두 개의 포인터를 사용하고 보통 교환이 더 적어 실제로 더 빠르지만, 분할 단계에서 피벗을 최종 위치에 놓지는 않습니다.
관련 자료
더 많은 시각화
