[c++] 퀵정렬

12 Dec 2023

퀵정렬(Quick Sort)은 정렬 알고리즘 중 하나로, 분할 정복 알고리즘의 한 예입니다. 배열을 특정한 기준 값(pivot)을 기준으로 분할하고 각 부분을 재귀적으로 정렬하는 방식으로 동작합니다. 이 알고리즘은 평균적으로 가장 빠른 정렬 알고리즘 중 하나로 알려져 있습니다.

코드 예시

아래는 C++로 구현된 퀵정렬의 간단한 예시 코드입니다.

#include <iostream>
#include <vector>

void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pivot = arr[high];
        int i = low - 1;
        
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                std::swap(arr[i], arr[j]);
            }
        }
        
        std::swap(arr[i + 1], arr[high]);
        
        int pivotIndex = i + 1;
        
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

int main() {
    std::vector<int> arr = {5, 2, 9, 3, 7, 6};
    int n = arr.size();
    
    quickSort(arr, 0, n - 1);
    
    std::cout << "Sorted array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    return 0;
}

위의 코드는 입력 배열을 정렬하는 데에 퀵정렬 알고리즘을 사용한 예시입니다. 크기가 N인 배열을 퀵정렬하는 데에는 일반적으로 평균적으로 O(NlogN) 시간 복잡도가 소요됩니다.

요약

퀵정렬은 효율적인 정렬 알고리즘이나, 최악의 경우에는 O(N^2)의 시간 복잡도를 가질 수 있으므로 이 점을 주의해서 사용해야 합니다. 또한 추가적인 메모리를 사용하지 않는 제자리 정렬(In-place Sorting) 알고리즘이기 때문에 배열을 정렬하는 데에 용이합니다.

더 자세한 정보는 여기에서 확인할 수 있습니다.