[Algorithm] Sorting / Quick Sort

Quick Sort(퀵 정렬)

• 퀵 정렬은 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법입니다.
• 퀵 정렬은 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속합니다.

알고리즘 진행 과정

먼저, 퀵 정렬은 분할 정복방법을 통해 리스트를 정렬합니다.

• 1. 리스트 가운데서 원소를 하나 고릅니다. 이렇게 고른 원소를 피벗(pivot)이라 합니다. (저의 코드에서는, 저는 배열의 가장 맨 앞 원소를 피벗으로 정했습니다.)
• 2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눕니다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 합니다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않습니다.
• 3. 분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복합니다. 재귀는 리스트의 크기가 1이 될 때까지 반복합니다.

재귀 호출이 한 번 진행될 때마다 피벗으로 정한 원소의 위치가 정해지게 됩니다!

먼저, 제 c++ 코드는 다음과 같습니다.
(제 코드는 다른 곳에서 배껴온 것이 아닌, 제가 직접 짜고 테스트 케이스도 직접 돌린 코드입니다. 이 외에 가져온 코드가 있으면 출처를 명확히 표기하겠습니다.)

#include <iostream>
using namespace std;

void QuickSort(int a[], int left, int right){
    int pivot = a[left]; // pivot은 배열의 가장 왼쪽 값을 선택한다고 가정
    int l = left+1, r = right; // 움직일 두 개의 포인터

    while(l <= r){
        while(a[l] < pivot && l<=right) l++;
        while(a[r] > pivot && r>=left) r--;

        if(l<r) swap(a[l], a[r]);
        if(l>=r){
            swap(a[left], a[r]); // r의 idx가 pivot의 자리
            break; // pivot의 위치를 찾았으므로 break
        }
    }

    if(left < r-1) QuickSort(a, left, r-1);
    if(r+1 < right) QuickSort(a, r+1, right);
}

int main(){
    int a[10]={5, 10, 1, 8, 7, 6, 4, 3, 2, 9};
    QuickSort(a, 0, 9);

    for(int i=0; i<10; i++) cout<<a[i]<<" ";
    cout<<endl;
    return 0;
}

먼저, QuickSort를 한 번 수행할 때마다, pivot의 위치가 결정됩니다.
그리고 결정된 pivot을 중심으로 리스트가 두 개로 나뉘게 되는데,
이때 리스트의 원소가 2개 이상이 되어야 재귀 호출이 진행됩니다.
즉, 원소가 1개인 경우, 더 이상 재귀가 진행되지 않습니다.

• 재귀의 탈출 조건: 원소가 1개 이하인 경우

좀 더 QuickSort 함수 내부를 살펴보면 다음과 같습니다.

l과 r는 두 개의 포인터이고(배열의 인덱스를 나타냅니다),
피벗을 기준으로 피벗의 왼쪽에는 피벗보다 작은 값들,
피벗을 기준으로 피벗의 오른쪽에는 피벗보다 큰 값들을 모으기 위해 다음과 같은 과정을 진행합니다.

int pivot = a[left]; // pivot은 배열의 가장 왼쪽 값을 선택한다고 가정
    int l = left+1, r = right; // 움직일 두 개의 포인터

    while(l <= r){
        while(a[l] < pivot && l<=right) l++;
        while(a[r] > pivot && r>=left) r--;

        if(l<r) swap(a[l], a[r]);
        if(l>=r){
            swap(a[left], a[r]); // r의 idx가 pivot의 자리
            break; // pivot의 위치를 찾았으므로 break
        }
    }

l은 피벗보다 큰 값이 있는지 찾고, r은 피벗보다 작은 값이 있는지 찾으면서,
찾고 난 이후,

• l < r 인 경우: a[l]과 a[r]의 값을 바꿔준다
• l >= r 인 경우: a[left]과 a[r]의 값을 바꿔준다

l>=r인 경우가, a[left] 즉 피벗의 위치를 찾은 경우이므로,
이 때는 a[left]와 a[r]을 바꾼 후 탈출합니다.

퀵 정렬의 시간복잡도

• 최악의 경우: O(n^2) (ex: 피벗을 가장 큰 값 또는 가장 작은 값을 골랐을 경우)
• 평균: O(nlogn), 일반적인 경우 퀵 정렬은 다른 O(nlogn) 알고리즘에 비해 훨씬 빠르게 동작합니다.