[퀵 정렬] 피벗으로 나누고 빠르게 정복하는 정렬 알고리즘

728x90

퀵 정렬(Quick Sort) 

퀵 정렬(Quick Sort)은 평균적으로 가장 빠르게 동작하는 정렬 알고리즘으로 알려져 있으며, 분할 정복(Divide and Conquer) 전략을 기반으로 합니다. 리스트에서 기준 값(피벗, pivot)을 정한 후, 피벗보다 작은 값과 큰 값을 나누어 각각을 재귀적으로 정렬하는 방식입니다.

이 알고리즘은 in-place 정렬이 가능하고, 평균 시간 복잡도가 O(n log n)으로 매우 우수하기 때문에 실무에서도 널리 사용되며, 다양한 언어의 표준 라이브러리에도 활용됩니다. 다만, 피벗 선택이 좋지 않으면 최악의 경우 O(n²)까지 성능이 떨어질 수 있어 그에 대한 보완 전략도 함께 알아둘 필요가 있습니다.

 

---

1.  퀵 정렬이란?

Quick Sort

 

퀵 정렬은 기준이 되는 값을 하나 정한 뒤, 그 값을 기준으로 작은 값과 큰 값을 나누고, 나뉜 그룹을 다시 같은 방식으로 정렬해나가는 알고리즘입니다. 이 과정을 반복하다 보면 전체 데이터가 정렬된 상태가 됩니다.

작동 방식

1. 리스트에서 하나의 피벗(Pivot)을 선택
2. 리스트를 피벗을 기준으로 작은 값과 큰 값으로 분할
3. 각각의 부분 리스트에 대해 퀵 정렬을 재귀적으로 수행
4. 모든 분할이 완료되면 리스트는 정렬된 상태가 됨

장점

• 평균적으로 매우 빠름 (O(n log n))
• 메모리 사용이 적은 제자리 정렬
• 대부분의 실무 상황에서 성능 우수

단점

• 불안정 정렬 (같은 값의 상대적 순서가 바뀔 수 있음)
• 최악의 경우 O(n²)
• 재귀 깊이가 깊어지면 스택 오버플로우 발생 가능

 

---

2.  예시

초기 배열 : [5, 3, 8, 4, 2, 7, 1, 6]

1. 피벗 : 5
2. 피벗보다 작은 값들 : [3, 4, 2, 1]
   피벗보다 큰 값들 : [8, 7, 6]
3. 이 두 그룹을 다시 퀵 정렬 → 재귀적으로 진행
4. 정렬 완료 후 합치면 : [1, 2, 3, 4, 5, 6, 7, 8]

 

---

3.  언어별 구현 예제

a.  Python (재귀적 구현)

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    left = [x for x in arr[1:] if x <= pivot]
    right = [x for x in arr[1:] if x > pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)

b.  C++

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);
    }
}

c.  Java

int partition(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++;
            int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
        }
    }
    int temp = arr[i+1]; arr[i+1] = arr[high]; arr[high] = temp;
    return i + 1;
}

void quickSort(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);
    }
}

d.  JavaScript

function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const pivot = arr[0];
  const left = arr.slice(1).filter(v => v <= pivot);
  const right = arr.slice(1).filter(v => v > pivot);
  return [...quickSort(left), pivot, ...quickSort(right)];
}

 

---

4.  시간 복잡도 분석

케이스	시간 복잡도
최선	O(n log n)
평균	O(n log n)
최악	O(n²)
공간 복잡도	O(log n) (재귀 깊이)
정렬 안정성	불안정 정렬

• 최악의 경우 : 이미 정렬된 상태에서 피벗을 가장 작거나 큰 값으로 선택할 때 발생합니다.
• 피벗 선택을 무작위로 하거나 Median of Three 전략을 사용해 최악 케이스를 방지하는 것이 가능합니다.

 

---

5.  퀵 정렬과 병합 정렬의 차이

분할 정복 공통 흐름

분할 정복 알고리즘은 공통적으로 다음 구조를 따릅니다:

1. 문제를 더 작은 문제로 분할
2. 작은 문제들을 각각 해결
3. 해결한 결과들을 다시 병합

a.  퀵 정렬의 분할 정복

• 분할 : 피벗 기준으로 좌/우 그룹 나누기
• 정복 : 양쪽 그룹에 퀵 정렬 재귀 수행
• 병합 : 병합 생략 (스왑 기반 정렬이므로)

b.  병합 정렬의 분할 정복

• 분할 : 중간 인덱스로 리스트 나누기
• 정복 : 양쪽 각각 병합 정렬 재귀 수행
• 병합 : 정렬된 두 리스트를 병합하여 하나로 만들기

 

---

6.  마무리

• 퀵 정렬은 분할 정복 방식을 사용하는 매우 빠른 정렬 알고리즘입니다.
• 피벗을 기준으로 좌우를 분할하고 재귀적으로 정렬합니다.
• 평균적으로 O(n log n)의 성능을 보이며, 실무에서도 널리 사용됩니다.
• 다만 최악의 경우 성능이 급격히 나빠질 수 있으므로 피벗 선택 전략이 중요합니다.
• 불안정 정렬이므로 상황에 따라 병합 정렬 등과 비교하여 선택해야 합니다.

함께 보면 좋은 자료

외부 사이트 :

• Wikipedia - Quick Sort

블로그 글 :

[정렬] 꼭 알아야 할 7가지 정렬 알고리즘 비교 정리

[병합 정렬] 나누고 정렬하고 다시 합치는 정렬의 정석

 

---

반응형