[ 알고리즘 ] 기준값에 의한 분할

알고리즘 목적

기준값(pivot, 피벗)을 기준으로 배열을 분할하는 알고리즘이다. 배열을 피벗보다 낮은 영역과 피벗보다 큰 영역으로 나눈다. 영역을 나눈 후에 피벗을 자기 자리에 배치한다.

기준값을 기준으로 배열을 분할한다고 해서 반드시 정렬되어야 하는 것은 아니다.

시간복잡도는 Θ(N)이다.

알고리즘 구현

동작과정

1. pivot을 정한다
2. pivot보다 작은 값을 발견할 경우, 왼쪽 영역을 확장하고 자리를 교체한다.
3. 모든 데이터를 순회했으면 pivot을 배치한다.

구현

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

void Print(vector<int> &arr) {
    for (int i = 0; i < arr.size(); i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    vector<int> arr = {5, 2, 7, 3, 8, 5, 6, 4};
    // vector<int> arr = { 2, 8, 7, 1, 3, 5, 6, 4 };
    // vector<int> arr = { 9, 8, 7, 6, 4, 3, 2, 1, 5 };
    // vector<int> arr = { 5, 2, 7, 3, 4, 4, 6, 4 };

    int lo = 0;              // 첫 인덱스
    int hi = arr.size() - 1; // 마지막 인덱스
    int x = arr[hi];         // 분할 기준으로 사용하는 pivot 4

    int i = lo - 1; // pivot보다 것들중 가장 큰 인덱스

    Print(arr);

    // COMPLETE:
    // NOTE: 배열의 영역을 나누기 위해 작은 값을 담당하는 영역의 포인터와 큰 값을 담당하는 영역와 배열 전체를 순회하는
    // 포인터를 사용

    for (int j = lo; j < hi; j++) {
        if (arr[j] < x) {
            swap(arr[++i], arr[j]);
        }
    }

    swap(arr[i + 1], arr[hi]);
    Print(arr);

    cout << i + 1 << endl; // 피벗 이하인 값들의 마지막 인덱스
}