추적값(pivot)을 활용한 분할 알고리즘

문제

특정 값을 기준으로 배열을 두개의 영역으로 분할하려고 한다. 특정값을 pivot이라고 하자. pivot을 기준으로 pivot보다 작은 값들과 pivot보다 큰값들이 모인 영역으로 배열을 분할한다.

 

아이디어

구현의 편의상 배열의 맨 끝 원소를 pivot으로 삼는다. pivot보다 작지만 가장 마지막에 배치 된 원소의 인덱스를 i, 배열을 순회하는 인덱스를 j, 배열의 첫번째 인덱스를 lo, 마지막 index를 hi라고 하자.

• 포인터 j가 배열 전체를 순회한다.
• j가 가리키는 값이 pivot보다 작다면 i를 값을 1만큼 증가한 후에 j의 값과 교체한다. 교체 후에 j를 전진시킨다.
• j가 가리키는 값이 pivot보다 크다면 j를 전진시킨다.
• j가 pivot에 도달할 때까지 반복한다.
• j가 pivot에 도달하면 i + 1 번째 원소와 위치를 교체한다.

pivot이 위치를 교체한 결과, pivot의 왼쪽은 pivot보다 작은 값들이, pivot의 오른쪽에는 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);

    // REVIEW
    for (int k = lo; k < hi; k++) { // i: 현재 검사하는 위치
        if (arr[k] <= x) {
            swap(arr[k], arr[++i]);
        }
    }

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

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