quicksort.py

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

    def helper(self, nums, left, right):
        if len(nums) <= 1: return
        if left > right:
            return

        mid_index = self.partition(nums, left, right)
        self.helper(nums, left, mid_index - 1)
        self.helper(nums, mid_index + 1, right)


    def partition(self, nums, left, right):
        done = False

        pivot_value = nums[left]

        left_index = left + 1
        right_index = right
        while not done:
            while left_index <= right_index and nums[left_index] <= pivot_value:
                left_index += 1

            while nums[right_index] >= pivot_value and left_index <= right_index:
                right_index -= 1

            if left_index >= right_index:
                done = True
            else:
                # exchange left value and right value
                nums[left_index], nums[right_index] = nums[right_index], nums[left_index]
        # exchange pivot_value with end
        nums[left], nums[right_index] = nums[right_index], nums[left]

        return right_index