Sort Colors
Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use 0 to represent red, 1 to represent white, and 2 to represent blue.
Constraints:
- You must not use the library's sort function.
- You must use a constant amount of space.
Examples:
Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Explanation: The input array contains 2 blues, 2 whites, and 2 reds. After sorting, the array should contain all the reds first, followed by the whites, and then the blues.
Solutions
Dutch National Flag Algorithm
The Dutch National Flag algorithm works by maintaining three pointers: left, right, and curr. The left pointer is used to track the position where the next 0 should be placed, the right pointer is used to track the position where the next 2 should be placed, and the curr pointer is used to scan the array. If the current element is 0, we swap it with the element at the left pointer and move both the left and curr pointers forward. If the current element is 2, we swap it with the element at the right pointer and move the right pointer backward. If the current element is 1, we simply move the curr pointer forward.
void sortColors(vector<int>& nums) {
int left = 0, right = nums.size() - 1, curr = 0;
while (curr <= right) {
if (nums[curr] == 0) {
swap(nums[left], nums[curr]);
left++;
curr++;
}
else if (nums[curr] == 2) {
swap(nums[right], nums[curr]);
right--;
}
else {
curr++;
}
}Follow-up:
How would you solve this problem if the array contained more than three colors?
