유명한 문제라고 한다. quick sort 에서 처럼 partitioning 에 입각한다.

3개의 ptr을 이용한다.

https://leetcode.com/problems/sort-colors/

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

in-place swap을 이용해서 풀이하면 된다. 물론 0, 1, 2 만 들어온다는 가정이 들어가 있다.

class Solution {
public:
	void sortColors(vector<int>& nums) {
		int left = 0; // left의 왼쪽에는 0만 있을 것이다.
		int right = nums.size() - 1; // right 의 오른쪽에는 2만 있을 것이다.
		int i = 0;  // 얘 가지고 swap 한다.

		while (i <= right)
		{
			if (nums[i] == 0)
			{
				int temp = nums[left];
				nums[left] = nums[i];
				nums[i] = temp;
				left++;
				i++;
			}
			else if (nums[i] == 2)
			{
				int temp = nums[i];
				nums[i] = nums[right];
				nums[right] = temp;
				right--;
			}
			else // 1이면 
			{
				i++;
			}
		}
	}
};