[C++로 배우는 알고리즘과 자료구조] Day 19: 퀵 정렬 (Quick Sort)

퀵 정렬 (Quick Sort)

퀵 정렬은 분할 정복(Divide and Conquer) 기법을 사용하는 효율적인 정렬 알고리즘입니다. 배열을 피벗(Pivot)을 기준으로 두 개의 하위 배열로 나눈 다음, 각각을 정렬합니다. 퀵 정렬은 평균적으로 매우 빠른 정렬 알고리즘으로 간주됩니다.

퀵 정렬의 시간 복잡도:

• 평균의 경우: (O(n \log n))
• 최악의 경우: (O(n^2))
• 최선의 경우: (O(n \log n))

퀵 정렬의 공간 복잡도:

• (O(\log n)) (재귀 호출 스택 공간)

퀵 정렬 구현

퀵 정렬의 주요 단계:

1. 분할 (Partition): 피벗을 기준으로 배열을 두 부분으로 나눕니다.
2. 정복 (Conquer): 하위 배열을 재귀적으로 정렬합니다.
3. 결합 (Combine): 분할된 하위 배열이 정렬된 상태이므로 추가적인 결합 단계는 필요 없습니다.

퀵 정렬의 구현 코드

#include <iostream>
#include <vector>

// 분할 함수
int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // 피벗을 배열의 마지막 요소로 설정
    int i = low - 1;

    for (int j = low; j <= high - 1; ++j) {
        if (arr[j] <= pivot) {
            ++i;
            std::swap(arr[i], arr[j]); // 피벗보다 작거나 같은 요소는 왼쪽으로 이동
        }
    }
    std::swap(arr[i + 1], arr[high]); // 피벗을 올바른 위치에 놓음
    return i + 1;
}

// 퀵 정렬 함수
void quickSort(std::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); // 오른쪽 하위 배열 정렬
    }
}

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

    std::cout << "정렬 전 배열: ";
    for (int value : arr) {
        std::cout << value << " ";
    }
    std::cout << std::endl;

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

    std::cout << "정렬 후 배열: ";
    for (int value : arr) {
        std::cout << value << " ";
    }
    std::cout << std::endl;

    return 0;
}

 

설명

1. 분할 함수 (Partition Function):
   • 피벗을 기준으로 배열을 두 부분으로 나눕니다.
   • 피벗보다 작거나 같은 요소는 왼쪽으로, 피벗보다 큰 요소는 오른쪽으로 이동시킵니다.
   • 피벗을 올바른 위치에 놓고 그 위치의 인덱스를 반환합니다.
2. 퀵 정렬 함수 (Quick Sort Function):
   • 분할 함수로 배열을 분할한 후, 재귀적으로 왼쪽 하위 배열과 오른쪽 하위 배열을 정렬합니다.

퀵 정렬의 기본 개념과 구현 방법을 이해했습니다. 다음 단계로 넘어가며, 더 복잡한 정렬 알고리즘과 다양한 알고리즘을 학습해보겠습니다.

질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 20: 힙 정렬"에 대해 학습하겠습니다.