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

📌퀵 정렬이란?

가장 빠른 정렬 알고리즘 중 하나. 분할 정복 방법이 적용된 알고리즘. 찰스 앤터니 리처드 호어(C. A. R. Hoare)가 알고리즘의 정렬 속도가 매우 빠르다고 해서 붙인 이름이다. 배열 내의 특정 데이터(pivot)를 기준으로 정렬할 데이터들을 왼쪽 부분 배열과 오른쪽 부분 배열로 나누어 각 부분 배열에 대해 퀵 정렬을 순환으로 적용하여 배열 전체를 정렬한다. 

 

📌시간 복잡도

최악: O(n^2) 이미 정렬되어 있는 배열을 정렬할 경우

최선: O(n log n)

평균: O(n log n)

 

 

📌흐름

1. 입력된 데이터 수가 n인 배열 `arr`가 있을 때 `arr` 내 임의의 데이터 피벗(pivot)을 정한다. 일반적으로 배열의 첫번째 데이터(`arr[0]`)가 된다.

2. 피벗을 기준으로 왼쪽 배열(피벗보다 작은 배열)과 오른쪽 배열(피벗보다 큰 배열)로 나눈다.

   2-1. 정수형 변수 `left`를 1, `right`를 n-1로 선언한다.

   2-2. `left`는 1씩 증가하면서 피벗보다 큰 값을 가진 데이터를 찾는다.(피벗보다 큰 값을 가진 데이터의 인덱스가 된다.)

   2-3. `right`는 1씩 감소하면서 피벗보다 작은 값을 가진 데이터를 찾는다.(피벗보다 작은 값을 가진 데이터의 인덱스가 된다.)

   2-4. 앞선 2와 3 과정을 만족했으면 `arr[left]`의 위치와 `arr[right]`의 위치를 서로 교환한다.

   2-5. `left`와 `right`가 서로 동일한 값이 되었을 때, 즉 `arr[left]`와 `arr[right]`가 같은 요소를 가리키면 *`arr[left]`와 `arr[right]`를 교환한다.

3. `left`가 `right`보다 커지면 피벗(`arr[0]`)과 `arr[right]`를 교환한다.

4. 왼쪽 배열과 오른쪽 배열에 대해 퀵 정렬을 재귀 호출한다.

 

 *동일한 요소를 교환하는 시도가 의미 없어 보일 수 있으나 이 시도는 아무리 많아야 1회이므로 `left`와 `right`가 동일한 요소 위에 있는지 검사하는 비용보다 적다.

 

 

 

📌구현

언어: C++

#include <iostream>

using namespace std;

template <class T>
void Swap(T* a, T* b) {
    T temp = *a;
    *a = *b;
    *b = temp;
}

template <class T>
void QuickSort(T* arr, int low, int high) {
    if (low >= high) return;  // 종료 조건

    T pivot = arr[high];  // 피벗을 맨 오른쪽 요소로 설정
    int left = low;
    int right = high - 1;  // 피벗 제외

    while (left <= right) {
        // 피벗보다 작으면 커서 오른쪽으로 이동
        while (left <= right && arr[left] < pivot) left++;
        // 피벗보다 크면 커서 왼쪽으로 이동
        while (left <= right && arr[right] > pivot) right--;

        if (left <= right) {
            Swap(&arr[left], &arr[right]);
            left++;
            right--;
        }
    }

    // 피벗 이동
    Swap(&arr[left], &arr[high]);

    // 피벗을 기준으로 두 부분으로 나누어 재귀 호출
    if (low < left - 1) QuickSort(arr, low, left - 1);
    if (left + 1 < high) QuickSort(arr, left + 1, high);
}

int main() {
    int arr[] = { 9, 6, 7, 3, 5 };
    int size = sizeof(arr) / sizeof(arr[0]);

    QuickSort(arr, 0, size - 1);

    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }

    cout << endl;
    return 0;
}