Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

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

Example

Given [1, 0, 1, 2], sort it in-place to [0, 1, 1, 2].

Solution

two solutions, but the second one is better.

(1) Rainbow Sort

O(kn) time + O(1) space

(2) Counting Sort

O(n) time O(k) space

(3) Partition

the big difference with Partition is , partition is only to add numbers to left and right , no matter about the sorting , but for this question is not , we need to do the range sort , like this way, 0000011111222222, left middle , right, we use middle as our baseline.

class Solution:
    """
    @param nums: A list of integer which is 0, 1 or 2 
    @return: nothing
    """
    def sortColors(self, nums):
        # write your code here
        n = len(nums)

        left, middle, right = 0, 0, n - 1

        while middle <= right:
            if nums[middle] == 0:
                nums[left], nums[middle] = nums[middle], nums[left]
                left += 1
                middle += 1

            elif nums[middle] == 1:
                middle += 1
            else:
                nums[middle], nums[right] = nums[right], nums[middle]
                right -= 1