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

퀵 정렬 (Quick Sort)

개념

퀵 정렬은 분할 정복 알고리즘의 일종이다. 피벗(Pivot)이라 하는 기준점을 잡고 배열을 나눈 뒤 정렬한다. 평균 시간복잡도가 O(n log n)이지만, 최악의 경우 O(n²)이 될 수도 있다.

과정

기준: 기준을 가지고 피벗 하나를 선택한다.

분할: 피벗을 기준으로 피벗보다 작은 원소는 왼쪽에, 큰 원소는 오른쪽에 배치한다.

정렬: 피벗을 기준으로 나눈 왼쪽 부분과 오른쪽 부분에 대해 각각 다시 정렬을 수행한다.

예시


                        [9, 7, 5, 11, 12, 2, 14, 3, 10, 6] // 피벗: 9
                       
                       [7, 5, 2, 3, 6] [9] [11, 12, 14, 10] // 피벗: 7, 11
                       
                 [5, 2, 3, 6] [7]      [9]   [10] [11] [12, 14] // 피벗: 5, 12
                 
           [2, 3] [5] [6]     [7]      [9]   [10] [11] [12] [14] // 피벗: 2
           
        [2] [3]   [5] [6]     [7]      [9]   [10] [11] [12] [14] // 종료

특징

추가 메모리 공간이 거의 필요하지 않아 효율적이고, 큰 데이터 세트를 정렬할 때 매우 빠르다.

피벗을 어떻게 선택하느냐&데이터의 정렬 상태에 따라 시간 복잡도가 다르다. 최악의 경우 O(n²)이 될 수 있고, 재귀로 분할정렬하기 때문에 오버플로우를 조심해야 한다.

구현 예시


#include <iostream>
#include <vector>
using namespace std;

void QuickSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;

    int pivot = arr[(left + right) / 2];
    int i = left;
    int j = right;

    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
            swap(arr[i], arr[j]);
            i++;
            j--;
        }
    }

    QuickSort(arr, left, j);
    QuickSort(arr, i, right);
}


int main() {
	vector<int> numbers = { 13, 45, 2, 27, 36, 8, 50, 22, 31, 11, 17, 43, 6, 28, 19, 4, 35, 46, 14, 24, 9, 33, 1, 38, 10, 42, 16, 25, 7, 34 };
    QuickSort(numbers, 0, numbers.size() - 1);
	for (int num : numbers) {
		cout << num << " ";
	}

	return 0;
}