[Algorithm] Quick sort / 퀵 정렬

1. Quick sort

• 분할 정복 테크닉을 사용한 매우 빠른 시간 복잡도를 가진 정렬 알고리즘이다. 
• 정렬 로직 수행 간 초기 정렬 상태를 보장하지 않는 불안정 정렬이다.
• 추가 메모리 공간을 필요로 하지 않는다.
• 시간 복잡도 : O(NlogN)

Quick sort의 로직 동작 과정

1. 주어진 배열의 범위 내에서 하나의 값(Pivot)을 기준으로 정하고, pivot 왼쪽에는 pivot보다 작은 값들이 오른쪽에는 pivot보다 큰 값들이 오도록 정렬한다.
2. pivot을 기준으로 나뉜 배열은 정렬된 순서는 보장하지 않기 때문에 각각 배열에서 새로운 pivot을 설정하여 다시 분할해서 재귀 호출 한다.
3. 1,2번의 과정을 배열을 분할할 수 없을 때 까지 반복한다.

출처 : https://akdl911215.tistory.com/386

Quick sort 장/단점

장점

 - pivot과 거리가 먼 데이터를 교환하기 때문에 이동시간이 소모되지 않고, 결정된 피벗을 기준으로 재귀 분할하기 때문에 연산에서 제외되어 다른 O(NlogN)의 시간복잡도를 가진 정렬 알고리즘과 비교해도 더 빠르다.

- 주어진 데이터 내에서 값 비교를 통해 교환하는 방식이기 때문에 추가적인 메모리가 필요하지 않다.

단점

- 불안정 정렬이기 때문에 초기의 정렬상태가 깨진다.

- 정렬된 배열을 Quick sort로 정렬할 경우 불균형 분할에 의해(뒤에서부터 다 확인해야 함) 오히려 느려질 수 있다. 최악의 경우 시간복잡도는 O(N^2)이 나온다.

---

2. Code

#include <bits/stdc++.h>

using namespace std;

vector<int> arr;

void Print() {
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << ' ';
    }
    cout << "\n";
}

int division(int left, int right) {
    int mid = (left + right) / 2;
    
    swap(arr[left], arr[mid]);
    int pivot = arr[left];
    int i = left;
    int j = right;

    while(i < j) {
        //오른쪽부터 pivot보다 작은애들 찾기
        //작은애들을 먼저 찾아야 pivot과 swap할 때 중간값을 기준으로 정렬이 됨.
        while(pivot < arr[j]) {
            j--;
        }
        //왼쪽부터 pivot보다 큰 애들 찾기
        //i < j를 넣어줌으로써 한 인덱스로 수렴이 됨.
        //i == j면 루프를 안들어오기 때문에 값은 결국 pivot보다 작은 값으로 수렴됨.
        while(i < j && pivot >= arr[i]) {
            i++;
        }

        swap(arr[i], arr[j]);
    }

    //현재 i를 기준으로 왼쪽에는 pivot보다 작은 값들이, 
    //오른쪽에는 pivot보다 큰 값들이 순서상관없이 정렬되어 있다.
    //처음에 바꿔준 pivot과 pivot보다 작은 값을 swap하면
    //배열상에서도 i를 기준으로 좌측은 i보다 작은값 우측은 i보다 큰 값만 존재
    swap(arr[left], arr[i]);

    //i를 기준으로 좌, 우는 값만 작다 크다로 나눠져있지 순서는 보장되지 않기 때문에
    // 분할을 통해 다시 좌, 우의 순서를 맞추기위해 i를 기준으로 나눠서 재귀를 호출해야 한다
    return i;
}

void quickSort(int left, int right) {
    //기저조건 : 하나의 원소로 수렴하면 return
    if(left >= right) return;

    //기준점을 받아와서
    int pivot = division(left, right);

    //이 pivot을 기준으로 좌, 우 분할 정복때리기
    quickSort(left, pivot-1);
    quickSort(pivot+1, right);
}

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        arr.push_back(rand() % 100);
    }

    clock_t start, finish;
    double duration;
    start = clock();

    quickSort(0, arr.size()-1);

    finish = clock();
    duration = (double)(finish - start) / CLOCKS_PER_SEC;
    Print();
    cout << "Quick sort로 " << n << "개 원소 정렬에 걸린 시간 " << duration << "초" << "\n";
}