퀵 소트

퀵 소트(Quick Sort)

---

퀵 소트란?

매우 효율적인 정렬 알고리즘
분할 정복(Divide and Conquer)방식을 기반을 가짐

기본 개념

리스트에서 하나의 요소를 피벗(pivot)으로 지정한 뒤 피벗을 기준으로 리스트를 두 부분으로 나눔

1. 피벗보다 작은 요소들
2. 피벗보다 큰 요소들

이 과정을 재귀적으로 반복하여 전체 리스트를 정렬함

알고리즘 단계

1. 피벗 선택 : 리스트에서 하나의 요소를 피벗으로 선택
2. 분할 : 피벗을 기준으로 리스트를 두 부분으로 나눔
3. 정복 : 분할된 부분 리스트에 대해 재귀적으로 퀵소트를 적용
4. 결합 : 정렬된 부분 리스트들을 하나의 리스트로 합침

성능

• 평균 시간 복잡도 : O(nlogn)
• 최악의 시간 복잡도 : O(n^2) 이미 정렬된 리스트에 대해 첫 번째 또는 마지막 요소를 피벗으로 선택할 경우
• 공간 복잡도 : O(logn)

퀵소트는 평균적으로 O(nlogn)으로 빠르게 동작하며, 추가적인 메모리 공간을 거의 필요로 하지 않음

구현

#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 pi = i + 1;

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    std::vector<int> arr = {10, 7, 8, 9, 1, 5};
    quickSort(arr, 0, arr.size() - 1);

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

    return 0;
}

고려 사항

피벗 선택 : 중간 값을 피벗으로 선택하거나 랜덤화를 통해 최악의 경우를 피할 수 있음

작은 부분 배열 처리 : 크기가 작은 부분 배열에 대해서는 삽입 정렬과 같은 다른 알고리즘 사용 가능

메모리 관리 : 불필요한 복사를 막기 위해 참조를 사용