퀵 정렬 (Quick Sort) (C++)

퀵 정렬 (Quick Sort)

퀵 정렬은 분할 정복(Divide and Conquer) 알고리즘의 한 종류로, 배열을 특정 기준(Pivot)을 중심으로 두 부분으로 나누고, 각각의 부분을 재귀적으로 정렬하는 방식. 일반적으로 매우 빠르고 효율적이기 때문에, 실무와 코딩 테스트에서 자주 사용.

---

동작 원리

1. 배열에서 하나의 요소를 Pivot으로 선택.
2. Partitioning:
   • Pivot보다 작은 값들은 왼쪽에, 큰 값들은 오른쪽에 배치.
3. Pivot을 기준으로 왼쪽과 오른쪽 서브 배열을 나눈다.
4. 왼쪽과 오른쪽 서브 배열에 대해 재귀적으로 퀵 정렬을 수행.
5. 모든 배열이 정렬될 때까지 반복.

---

특징

• 시간 복잡도:
  • 평균: O(nlog⁡n)
  • 최선: O(nlog⁡n) (Pivot이 항상 중앙값일 때)
  • 최악: O(n^2) (Pivot이 최솟값 또는 최댓값일 때, 이미 정렬된 배열에서 발생 가능)
• 공간 복잡도: O(log⁡n) (재귀 호출로 인한 스택 사용량)
• 비안정적 정렬: 동일한 값의 순서가 바뀔 수 있음.
• 실용성: 일반적으로 매우 빠르고 효율적, 특히 평균 시간 복잡도가 낮아 대규모 데이터 정렬에 적합.

---

예제 코드 (C++)

오름차순 퀵 정렬 구현

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

// Partition 함수: 배열을 분할하고 Pivot의 최종 위치를 반환
int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];  // 마지막 요소를 Pivot으로 선택
    int i = low - 1;        // 작은 요소가 들어갈 위치

    for (int j = low; j < high; ++j) {
        if (arr[j] < pivot) {  // Pivot보다 작으면
            ++i;
            swap(arr[i], arr[j]);  // 작은 값을 왼쪽으로 이동
        }
    }
    swap(arr[i + 1], arr[high]);  // Pivot을 적절한 위치로 이동
    return i + 1;  // Pivot의 최종 위치 반환
}

// 퀵 정렬 함수: 재귀적으로 배열을 정렬
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);  // Pivot의 위치
        quickSort(arr, low, pi - 1);         // 왼쪽 부분 정렬
        quickSort(arr, pi + 1, high);        // 오른쪽 부분 정렬
    }
}

int main() {
    vector<int> arr = {10, 7, 8, 9, 1, 5};
    cout << "정렬 전 배열: ";
    for (int num : arr) cout << num << " ";
    cout << endl;

    quickSort(arr, 0, arr.size() - 1);

    cout << "정렬 후 배열: ";
    for (int num : arr) cout << num << " ";
    cout << endl;

    return 0;
}

---

코드 설명

1. partition 함수:
   • 배열을 Pivot 기준으로 두 부분으로 나눈다.
   • Pivot보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 배치.
   • Pivot의 최종 위치를 반환하여 이후 재귀 호출에 사용.
2. quickSort 함수:
   • 재귀적으로 호출하며 배열의 왼쪽과 오른쪽을 각각 정렬.
3. Base Case:
   • low가 high 이상이 되면 재귀 호출을 종료.

---

예제 동작 과정

입력 배열: [10, 7, 8, 9, 1, 5]

1. 첫 번째 Partition (low=0, high=5):
   • Pivot: 5
   • 배열 분할 과정:
     • 10 > 5 → 그대로.
     • 7 > 5 → 그대로.
     • 8 > 5 → 그대로.
     • 9 > 5 → 그대로.
     • 1 < 5 → 교환 → [1, 7, 8, 9, 10, 5]
   • Pivot 위치 이동 → [1, 5, 8, 9, 10, 7] (Pivot=5 위치: 1)
   • 결과: [1, 5, 8, 9, 10, 7]
2. 왼쪽 서브 배열 정렬 (low=0, high=0):
   • 정렬 완료 (원소 1개).
3. 오른쪽 서브 배열 정렬 (low=2, high=5):
   • Pivot: 7
   • 배열 분할 과정:
     • 8 > 7 → 그대로.
     • 9 > 7 → 그대로.
     • 10 > 7 → 그대로.
   • Pivot 위치 이동 → [1, 5, 7, 9, 10, 8] (Pivot=7 위치: 2)
   • 결과: [1, 5, 7, 9, 10, 8]
4. 다음 Partition (low=3, high=5):
   • Pivot: 8
   • 배열 분할 과정:
     • 9 > 8 → 그대로.
     • 10 > 8 → 그대로.
   • Pivot 위치 이동 → [1, 5, 7, 8, 10, 9] (Pivot=8 위치: 3)
   • 결과: [1, 5, 7, 8, 10, 9]
5. 최종 정렬된 배열: [1, 5, 7, 8, 9, 10]

---

장점과 단점

장점

• 평균 시간 복잡도가 O(nlog⁡n)으로 매우 빠름.
• 추가 메모리가 거의 필요하지 않음 (O(log⁡n)).
• 일반적으로 대부분의 데이터에 대해 효율적.

단점

• 최악의 경우 시간 복잡도가 O(n^2).
• 비안정적 정렬: 같은 값의 순서가 바뀔 수 있음.

---

활용 사례

• 대규모 데이터 정렬.
• 평균적으로 빠른 성능이 필요한 경우.