# Quicksort implementation in Python

I have written an implementation of Quicksort in Python. I am new to Python. Any suggestions for improvement or criticism on my use of Python?

def partition(a, lo, hi):
i, j, v = lo+1, hi, a[lo]
while(True):
while(a[i] < v):
i += 1
if (i == hi): break
while(a[j] > v):
j -= 1
if (j == lo): break
if (i >= j): break
a[i], a[j] = a[j], a[i]
a[lo], a[j] = a[j], a[lo]
return j

def sort(a, lo, hi):
if (hi <= lo):
return
q = partition(a, lo, hi)
sort(a, lo, q-1)
sort(a, q+1, hi)
assert isSorted(a, lo, hi)

def quick_sort(a):
shuffle(a)
sort(a, 0, len(a)-1)
assert isSortedArray(a)

def isSorted(a, lo, hi):
for i in range(lo, hi):
if a[i+1] < a[i]:
return False
return True

def isSortedArray(a):
for i in range(0, len(a)-1):
if a[i+1] < a[i]:
return False
return True

• Where are isSorted and isSortedArray? – jonrsharpe Nov 1 '14 at 9:01
• @jonrsharpe I don't think that the implementation of those functions is essential to the question. – 200_success Nov 1 '14 at 9:19
• @jonrsharpe They are just functions which check whether the array is sorted or not and returns a boolean. Just for assertion purpose. – khateeb Nov 2 '14 at 2:02

## 1 Answer

When describing quicksort partitioning, your v is typically called the "pivot". The code would be clearer if you named the variable according to that convention.

You always choose a[lo] as the pivot. However, that produces pathological performance when the input array is already sorted.

I would prefer to see

while(a[i] < v):
i += 1
if (i == hi): break


… written as

while i < hi and a[i] < pivot:
i += 1


Array index bounds usually work better when specified as inclusive-exclusive ranges, such that sort(a, lo, hi) means "sort a where lo ≤ index < hi". This is a common convention — you can see it in Python's range() and slicings. Also, Java's Arrays.sort(a, fromIndex, toIndex) works with inclusive-exclusive ranges.

Some nice properties of inclusive-exclusive ranges are:

• hi - lo gives you the number of elements in the range.
• When creating a range for the entire array a, hi is just len(a). You save a "-1".
• When splitting [lo, hi) into two consecutive ranges, it becomes [lo, mid) and [mid, hi). You save a "-1".
• In Python, you can conveniently write for i in range(lo, hi) for the most common type of iteration. (Admittedly, iterating backwards is uglier, but it's less common.)
• @200_success Thanks for your suggestions. I had shuffled the array in the beginning using Knuth shuffle algorithm. I was wondering whether a better approach would be to shuffle first and then use the first element as the pivot or choosing a random element or median as the pivot. – khateeb Nov 2 '14 at 2:14
• Shuffling before sorting seems wasteful. You would be better off choosing a random element or the median of three elements as the pivot. – 200_success Nov 2 '14 at 2:26
• Should my partition function be also inclusive-exclusive range? – khateeb Nov 2 '14 at 2:29
• Yes, I would recommend consistently using inclusive-exclusive ranges everywhere. – 200_success Nov 2 '14 at 2:31