[C++][구현] Sort Colors (배열 파티셔닝 문제)

배열안에는 {0, 1, 2}인 요소만 들어갈 수 있습니다.

이 배열을 O(n) 시간복잡도로 정렬을 하는 문제입니다.

 

 

counting

// 1. Counting O(n)
void SortColors(int nums[], int length) {

	int zero(0), one(0), two(0);
	
	for (int i = 0; i < length; i++)
	{
		switch (nums[i])
		{
		case 0:
			zero++;
			break;
		case 1:
			one++;
			break;
		case 2:
			two++;
			break;
		}
	}
	
	for (int i = 0; i < length; i++)
	{
		if (i < zero) nums[i] = 0;
		else if (i < zero + one) nums[i] = 1;
		else nums[i] = 2;
	}
}

기본적으로 배열에 어떠한 숫자가 있는지 갯수를 세어서 다시 정렬하는 방법입니다.

 

 

inplace_sort

// 2. inplace-swap
void SortColors(int nums[], int length) {
	int begin(0);
	int end(length - 1);
	int pivot(0);
	while (pivot <= end) {
		if (nums[pivot] == 0) {
			swap(nums[begin], nums[pivot]);
			pivot++;
			begin++;
		}
		else if (nums[pivot] == 2) {
			swap(nums[end], nums[pivot]);
			end--;
		}
		else
			pivot++;
	}
}

한 번 숫자를 확인 할 때, 한쪽으로만 넘길 수 있다는 생각에서, 양 끝 쪽도 정렬시킬 수 있다는 발상입니다.

 

Partion 문제로, Quick sort원리와 비슷합니다.