[자료구조] 분할

배열을 분할한다는 것은 배열로부터 임의의 수를 가져와(이 수를 피벗이라고 부름) 피벗보다 작은 모든 수는 피벗의 왼쪽에, 피벗보다 큰 모든 수는 피벗의 오른쪽에 두는 것이다. 

 

아래와 같은 배열이 있다고 하자.

일관된 설명을 위해 가장 오른쪽에 있는 값을 항상 피벗으로 하고 3을 이용해 분할해 보자.

두 개의 포인터를 사용해 하나는 배열 가장 왼쪽에 있는 값에, 다른 하나는 가장 오른쪽 있는 값에 할당한다. 분할은 다음의 단계를 따라 실제 분할한다.

1. 왼쪽 포인터를 한 셀씩 계속 오른쪽으로 옮기면서 피벗보다 크거나 같은 값에 도달하면 멈춘다.
2. 오른쪽 포인터를 한 셀씩 계속 왼쪽으로 옮기면서 피벗보다 작거나 같은 값에 도달하면 멈춘다.
3. 왼쪽 포인터와 오른쪽 포인터가 가리키고 있는 값을 교환한다.
4. 두 포인터가 가리키는 값이 같거나 왼쪽 포인터가 오른쪽 포인터 바로 오른쪽으로 이동할 때까지 위 과정을 반복한다.
5. 끝으로 왼쪽 포인터가 현재 가리키고 있는 값과 피벗을 교환한다.

분할이 끝나면 피벗 왼쪽에 있는 값은 모두 피벗보다 작고, 피벗 오른쪽에 있는 값은 모두 피벗보다 크다고 확신할 수 있다. 다른 값들은 정렬되지 않았지만 피벗 자체는 배열 내의 올바른 위치에 있다는 의미다.

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

class CSortArray
{
public:
	CSortArray() = default;
	CSortArray(vector<int>& arr)
	{
		array = arr;
	}

	int partition(int lptr, int rptr)
	{
		int pivot_pos = rptr;
		int pivot = array[pivot_pos];
		rptr--;

		while (true)
		{
			while (array[lptr] < pivot)
				lptr++;
			while (array[rptr] > pivot)
				rptr--;

			if (lptr >= rptr)
				break;
			else
				swap(lptr, rptr);
		}

		swap(lptr, pivot_pos);
		return lptr;
	}

	void swap(int ptr1, int ptr2)
	{
		int tmp_value = array[ptr1];
		array[ptr1] = array[ptr2];
		array[ptr2] = tmp_value;
	}

	vector<int> array;
};

int main()
{
	vector<int> testArr = { 0, 5, 2, 1, 6, 3 };
	CSortArray sortArr(testArr);
	sortArr.partition(0, testArr.size() - 1);

	for (int i = 0; i < (int)testArr.size(); i++)
		cout << testArr[i] << "\t";
	cout << endl;
	for (int i = 0; i < (int)sortArr.array.size(); i++)
		cout << sortArr.array[i] << "\t";
	cout << endl;

	return 0;
}

partition 메서드를 사용하여 pivot이 정확한 위치에 위치함을 알 수 있다.