앞서 배운 버블 정렬과 선택 정렬은 O(n^2)의 느린 속도 때문에 실제 현업에서는 거의 사용되지 않습니다. 그렇다면 Python의 `sort()`, Java의 `Arrays.sort()` 같은 내장 함수들은 도대체 어떤 마법을 쓰길래 순식간에 데이터를 정리해 줄까요? 그 비밀의 주인공이 바로 퀵 정렬(Quick Sort)입니다. 이름부터 '빠르다(Quick)'는 자신감이 넘치는 이 알고리즘은 '분할 정복(Divide and Conquer)'이라는 강력한 전략을 사용하여 평균적으로 O(n log n)이라는 압도적인 속도를 자랑합니다.
1. 퀵 정렬의 핵심 전략: 분할 정복
어려운 문제를 한 번에 풀려고 하면 머리가 아픕니다. 하지만 문제를 아주 작게 쪼개서 하나씩 해결하고 다시 합치면 의외로 쉽게 풀립니다. 이것이 분할 정복입니다. 퀵 정렬은 거대한 배열을 통째로 정렬하는 대신, 기준점(Pivot)을 하나 정해서 "기준보다 작은 그룹"과 "기준보다 큰 그룹"으로 반반씩 쪼개 나가는 방식을 취합니다.
2. 퀵 정렬의 동작 과정 (Partitioning)
퀵 정렬의 모든 마법은 '피벗(Pivot)'이라 불리는 기준 값을 정하는 데서 시작합니다. 보통 배열의 맨 앞, 맨 뒤, 혹은 중간값을 피벗으로 잡습니다.
2-1. 파티셔닝(Partitioning): 헤쳐 모여!
예를 들어 `[5, 3, 8, 4, 9, 1, 6]`이라는 배열이 있고, 맨 앞의 `5`를 피벗으로 잡았다고 가정해 봅시다. 1. 이제 `5`를 기준으로 나머지 숫자들을 검사합니다. 2. `5`보다 작은 숫자들은 왼쪽으로, `5`보다 큰 숫자들은 오른쪽으로 보냅니다. 3. 정리가 끝나면 `[3, 4, 1] - 5 - [8, 9, 6]`의 형태가 됩니다. 4. 이제 피벗이었던 `5`는 자기 자리를 완벽하게 찾았습니다. (왼쪽엔 자기보다 작은 놈들, 오른쪽엔 큰 놈들만 있으니까요!)
2-2. 재귀 호출(Recursion): 쪼개진 그룹에서 다시 시작
이제 `5`를 기준으로 나뉜 왼쪽 그룹 `[3, 4, 1]`과 오른쪽 그룹 `[8, 9, 6]`에 대해 똑같은 작업을 수행합니다. 왼쪽 그룹에서 다시 피벗을 정해 나누고, 오른쪽도 마찬가지입니다. 그룹의 크기가 0이나 1이 될 때까지 계속 쪼개면(재귀), 어느새 전체 배열이 정렬되어 있습니다.
3. 퀵 정렬이 빠른 이유 (Time Complexity)
퀵 정렬은 평균적으로 O(n log n)의 시간 복잡도를 가집니다. 이는 버블 정렬 같은 O(n^2) 알고리즘과 비교하면 천지 차이입니다. 100만 개의 데이터를 정렬할 때 O(n^2)은 1조 번 연산해야 하지만, O(n log n)은 약 2,000만 번이면 충분합니다.
3-1. 병합 정렬(Merge Sort)보다 빠른 이유?
이론적으로 병합 정렬도 O(n log n)입니다. 하지만 실제 컴퓨터에서 돌려보면 퀵 정렬이 더 빠를 때가 많습니다. 그 이유는 퀵 정렬이 '먼 곳에 있는 데이터를 교환'하고, 배열 내부에서 직접 자리를 바꾸는 방식(In-place Sort)이라 캐시 지역성(Cache Locality)이 좋기 때문입니다. 즉, 컴퓨터 하드웨어 친화적인 알고리즘입니다.
4. 퀵 정렬의 치명적 약점: 최악의 경우
하지만 퀵 정렬에도 아킬레스건이 있습니다. 만약 피벗을 항상 '가장 작은 값'이나 '가장 큰 값'으로만 잘못 고르면 어떻게 될까요? 예를 들어 이미 정렬된 `[1, 2, 3, 4, 5]`를 퀵 정렬하려고 할 때, 매번 맨 앞을 피벗으로 잡으면 그룹이 반으로 나뉘지 않고 `1`개와 `N-1`개로 나뉩니다. 이렇게 되면 분할 정복의 이점이 사라져 O(n^2)의 속도로 전락합니다. 그래서 실무에서는 피벗을 랜덤하게 잡거나, '중간값'을 피벗으로 선택하는 방식으로 이 문제를 방지합니다.
1. 퀵 정렬은 피벗(Pivot)을 기준으로 작은 값과 큰 값을 나누는 분할 정복 알고리즘입니다.
2. 평균적으로 O(n log n)의 매우 빠른 속도를 자랑하며, 실제 라이브러리에서 가장 많이 쓰입니다.
3. 이미 정렬된 데이터에서 피벗을 잘못 잡으면 O(n^2)으로 느려질 수 있어 주의가 필요합니다.