[정렬] 퀵 정렬

1. 설명

• pivot을 하나 설정하여 작은 값은 왼쪽, 큰 값은 오른쪽에 배치
• 평균적으로 O(n log n), 최악의 경우 O(n²)
• 메모리 추가 사용 없이 빠른 속도 제공 (제자리 정렬)

 

2. 코드

#include <iostream>
#include <vector>

using namespace std;

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) {
            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 pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

int main() {
    vector<int> arr = {64, 25, 12, 22, 11};
    quickSort(arr, 0, arr.size() - 1);

    for (int num : arr) cout << num << " ";
}