[Algorithm] 퀵 정렬(Quick sort) C++ 코드

퀵 정렬(Quick Sort)

비교 방식 알고리즘(Comparisons Sorting Algorithm)

퀵 정렬은 특정한 값인 피벗(Pivot)을 기준으로 큰 숫자와 작은 숫자를 구분하여 정렬한다. 퀵 정렬은 Sorting 알고리즘 중에 가장 빠르다고 하여 Quick이라는 이름이 붙여졌지만, Worst Case에서는 그렇지 않다. 퀵 정렬은 분할 정복 알고리즘을 이용하며 시간 복잡도는 평균 O(N * logN) 이지만 Worst Case에서는 O(n^2)의 시간복잡도를 갖는다.

#include <iostream>
#include <vector>

using namespace std;

vector<int> arr = {2, 8, 1, 3, 6, 4, 7, 5, 9};

void quickSort(int start, int end) {
    if (start >= end)
        return;
    int i = start + 1, j = end;
    while (i <= j) {
        while (i <= end && arr[i] <= arr[start]) {
            i++;
        }
        while (j > start && arr[j] >= arr[start]) {
            j--;
        }
        if (i > j) {
            int temp = arr[j];
            arr[j] = arr[start];
            arr[start] = temp;
        } else {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    quickSort(start, j - 1);
    quickSort(j + 1, end);
}
int main() {
    quickSort(0, arr.size() - 1);
    //출력
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

정렬과 관련해 다른 알고리즘을 배우고 싶다면 정렬 알고리즘(Sorting Algorithm) 포스트를 참고하길 바란다.