Implementing Quicksort in Python

Just like Mergesort, Quicksort is another favorite sorting algorithm with best case O(n logn) but worst case O(n^2). However, compare to merge sort, this algorithm doesn’t use extra space at all. Find the article on wikipedia if you haven’t seen this algorithm yet: https://en.wikipedia.org/wiki/Quicksort

The idea is as below:

  • Pick pivot number (any number, but someone said pick middle or random to minimize the worst case)
  • Reorder the array so that elements less than pivot come before the pivot, and elements greater than pivot come after. After this, pivot is in its final position. This process is called partitioning.
  • Recursively apply the above to sublists elements with smaller values and separately with greater values.
def quicksort(nums):
  sort(nums, 0, len(nums)-1)

def sort(nums, first, last):
  if first < last:
    pivot = partition(nums, first, last)
    sort(nums, first, pivot-1)
    sort(nums, pivot+1, last)

def partition(nums, first, last):
  pivot = first + (last - first + 1)/2
  swap(nums, pivot, last)
  for i in range(first, last):
    if nums[i] <= nums[last]:
      swap(nums, i, first)
      first += 1
  swap(nums, first, last)
  return first

def swap(nums, left, right):
  nums[left], nums[right] = nums[right], nums[left]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s