[c++] 퀵 정렬(Quick Sort) 알고리즘

08 Dec 2023

퀵 정렬은 분할 정복 알고리즘을 사용하여 정렬을 수행하는 방법 중 하나입니다. 이 알고리즘은 평균적으로 빠른 속도를 자랑하며, 많은 언어 및 라이브러리에서 기본적으로 사용됩니다.

알고리즘 원리

피벗(pivot)을 선택합니다. 피벗은 리스트의 요소 중 하나를 선택합니다.
피벗을 기준으로 리스트를 두 개의 부분으로 나눕니다. 작은 요소들은 피벗의 왼쪽에 위치하고, 큰 요소들은 오른쪽에 위치하게 됩니다.
각 부분에 대해 재귀적으로 퀵 정렬을 수행합니다.

예시 코드

아래는 C++로 작성된 퀵 정렬 알고리즘의 간단한 예시 코드입니다.

#include <iostream>
#include <vector>

void quickSort(std::vector<int>& arr, int left, int right) {
    int i = left, j = right;
    int pivot = arr[(left + right) / 2]; // 중간 요소를 피벗으로 선택
    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
            std::swap(arr[i], arr[j]);
            i++;
            j--;
        }
    }
    if (left < j) quickSort(arr, left, j);
    if (i < right) quickSort(arr, i, right);
}

int main() {
    std::vector<int> arr = {3, 6, 8, 10, 1, 2, 1};
    quickSort(arr, 0, arr.size() - 1);
    for (int num : arr) {
        std::cout << num << " ";
    }
    return 0;
}

참고 자료

퀵 정렬은 많은 컴퓨터 과학 기초 강의에서 다루는 주요한 알고리즘 중 하나이며, 학습과 이해를 위해 다양한 자료를 참고하는 것이 좋습니다.