Quick Sort

In-Place 방법을 사용하여 추가 메모리를 사용하지 않는다.

pivot은 배열의 가장 끝 원소로 설정한다.

배열의 시작 인덱스는 front, 끝 인덱스는 end라고 한다

 

front cursor는 front부터 end-1까지 탐색하여서 pivot보다 큰 수를 탐색한다

back cursor는 end - 1부터 front까지 탐색하여서 pivot보다 작은 수를 탐색한다.

	→					←		pivot
3	10	10	1	4	9	2	7	7

 

front와 back이 교차되지 않았다면 front의 원소와 back의 원소를 바꿔준다.

front와 back이 교차되었다면 front의 원소와 pivot의 원소를 바꿔준다.

 

front의 값을 정렬 후 pivot의 위치라는 점을 활용하여 재귀적으로 함수를 호출해준다.

 

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

int partition(vector<int>& data, int start, int end) 
{
    const auto& pivot = data[end];
    int front = start;
    int back = end - 1;
    while (front <= back)
    {
        while (front < end && data[front] <= pivot) front++;
        while (start <= back && data[back] > pivot) back--;
        if (front > back) swap(data[end], data[front]);
        else swap(data[front], data[back]);
    }
    return front;
}

void quicksort(vector<int>& data, int start, int end) 
{
    if (start >= end) 
    {
        return;
    }
    int pivot_pos = partition(data, start, end);
    quicksort(data, start, pivot_pos - 1);
    quicksort(data, pivot_pos + 1, end);
}

int main() 
{
    vector<int> data = { 3, 10, 10, 1, 1, 4, 9, 2, 7, 7 };
    quicksort(data, 0, data.size() - 1);
    cout << "퀵 소트 후 ---" << endl;
    for (int num : data) 
    {
        cout << num << " ";
    }
}