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

알고리즘 목적기준값(pivot, 피벗)을 기준으로 배열을 분할하는 알고리즘이다. 배열을 피벗보다 낮은 영역과 피벗보다 큰 영역으로 나눈다. 영역을 나눈 후에 피벗을 자기 자리에 배치한다.기준값을 기준으로 배열을 분할한다고 해서 반드시 정렬되어야 하는 것은 아니다.시간복잡도는 Θ(N)이다.알고리즘 구현동작과정pivot을 정한다pivot보다 작은 값을 발견할 경우, 왼쪽 영역을 확장하고 자리를 교체한다.모든 데이터를 순회했으면 pivot을 배치한다.구현#include #include using namespace std;void Print(vector &arr) { for (int i = 0; i arr = {5, 2, 7, 3, 8, 5, 6, 4}; // vector arr = { 2, 8, ..