퀵 정렬(Quick Sort)

개요

지금까지는 시간 복잡도 O(N^2)을 가지는 정렬을 다루어보았다. 하지만, 이러한 정렬 알고리즘은 데이터의 양이 방대해질수록 처리 속도가 느려지기에 그 성능이 떨어진다. 이를 보완할 수 있는 알고리즘이 바로 퀵 정렬이며, 각 언어에서 지원하는 sort 기능으로 이 알고리즘을 많이 사용한다.

퀵 정렬

"3 1 2 9 8 4 7 10 5 6
위 숫자들을 오름차순으로 정렬하라."

퀵 정렬은 하나의 기준값(pivot)으로 좌우를 살펴 조건에 맞게 스왑하는 방식이다. 그 과정에서 지속적으로 기준값을 갱신해나가며, 이 기준값에 따라 정렬하는 범위를 세부적으로 분할해나간다.

수행 과정

1. 기준값을 선정한다. (3 1 2 9 8 4 7 10 5 6)
2. 기준값의 왼쪽(기준 인덱스 + 1)에서부터 큰 값을 찾고, 오른쪽(전체 길이 - 1)에서부터 작은 값을 찾는다. (큰 값은 9, 작은 값은 2)
3. 기준값의 인덱스(0)가 작은 값의 인덱스(2)보다 작기 때문에 둘을 스왑한다. (2 1 3 9 8 4 7 10 5 6)
4. 이제 기준값을 기준으로 왼쪽에 위치하고 있는 숫자들끼리 1~3번 과정을 반복하고, 오른쪽에 위치하고 있는 숫자들끼리 1~3번 과정을 반복한다.
5. 이 과정을 거쳐 정렬하는 배열의 길이가 1이라면 정렬을 멈춘다.

시간 복잡도

퀵 정렬은 기준값으로 정렬하는 범위를 분할한다는 점에서 앞선 알고리즘들과 차이를 갖는다. 만약 데이터가 10개라면, 정렬이 끝날 때까지 10번의 반복횟수를 계속 거쳐야 하지만 퀵 정렬은 점점 세분화하여 10번이 5번이 되고 2번이 되어 그 횟수를 줄여나간다. 따라서 퀵 정렬의 시간 복잡도는 O(N * logN)이 된다. 하지만 이는 평균적인 경우이고, 이미 정렬이 완성된 최악의 경우 O(N^2)의 시간 복잡도를 가지게 된다.

코드 구현

#include <iostream>
#include <vector>

std::vector<int> array{3, 1, 2, 9, 8, 4, 7, 10, 5, 6};

std::vector<int> quick_sort(std::vector<int> array, int start, int end){
    if (start >= end) return array;

    std::vector<int> new_array, temp_array;

    int pivot = start;
    int i = start + 1;
    int j = end;

    while (i <= j) {
        while (i <= end && array[i] <= array[pivot]) i++;
        while (j > start && array[j] >= array[pivot]) j--;

        if (i >= j) {
            int temp = array[pivot];
            array[pivot] = array[j];
            array[j] = temp;
        }
        else {
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }

    temp_array = quick_sort(array, start, j - 1);
    new_array = quick_sort(array, j + 1, end);

    for (int i=0;i<j;i++){
        new_array[i] = temp_array[i];
    }

    return new_array;
}

int main(){
    std::vector<int> sorted_array = quick_sort(array, 0, array.size() - 1);

    for (int i=0;i<sorted_array.size();i++){
        std::cout<<sorted_array[i]<<' ';
    }

    return 0;
}
//1 2 3 4 5 6 7 8 9 10

Reference

https://m.blog.naver.com/PostView.naver?blogId=ndb796&logNo=221226813382&navType=by