Quick Sort

quickSort.py

from random import randint

def partition(nums, l, r, pIdx):
  
  pVal = nums[pIdx]

  # Swap pivot index with the right most
  nums[r], nums[pIdx] = nums[pIdx], nums[r]

  # Everything to the left of index i
  # will be less than the pivot value
  i = l
  
  for j in range(l,r): # Don't go all the way to end
    if nums[j] < pVal:
      nums[i], nums[j] = nums[j], nums[i]
      i += 1

  # Swap right most index with i
  # Because i is the correct position
  # for the pivot value in the sorted array
  nums[i], nums[r] = nums[r], nums[i]
  return i

def quickSortH(nums, l, r):

  if r <= l:
    return

  i = partition(nums, l, r, randint(l,r))

  quickSortH(nums, l, i - 1)
  quickSortH(nums, i + 1, r)

  return

def quickSort(nums):
  quickSortH(nums, 0, len(nums) - 1)

nums = [5, 3, 8, 6, 2, 1, 0, 9, 7, 4]

print nums
quickSort(nums)
print nums