75. Sort Colors

Given an array nums 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.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library’s sort function.

• insertion sort with binary search

class Solution {
public:
    void sortColors(vector<int>& nums) {
        for(int i = 1; i < nums.size(); i++) {
            if(nums[i] < nums[i - 1]) {
                swap(nums[upper_bound(nums.begin(), nums.begin() + i - 1, nums[i]) - nums.begin()], nums[i]);
                if(nums[i] < nums[i - 1]) {
                    swap(nums[upper_bound(nums.begin(), nums.begin() + i - 1, nums[i]) - nums.begin()], nums[i]);
                }
            }
        }
    }
};

class Solution {
public:
    void sortColors(vector<int>& nums) {
        for(int i = 1; i < nums.size(); i++) {
            for(int j = i; j > 0 and nums[j] < nums[j-1]; j--) {
                swap(nums[j], nums[j-1]);
            }
        }
    }
};