Sort Colors

Problem: Sort Colors

We use two pointers to implement quick-sort like sorting to solve this problem. We use one pointer to scan the array and another pointer points to last first non-zero numbers. Once we find a zero, we replace it with first non-zero number and move the second pointer ahead.

The second time we do the same thing to non-zero numbers. Since we've already put all zeros into left part of array, what's left are non-zero numbers. We sort 1 to left of this part by the same method.

Code in Python:

class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        j = 0
        for i in xrange(len(nums)):
            if nums[i] == 0:
                nums[i], nums[j] = nums[j], nums[i]
                j += 1
        for i in xrange(j, len(nums)):
            if nums[i] == 1:
                nums[i], nums[j] = nums[j], nums[i]
                j += 1