3
\$\begingroup\$

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

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.)
\$\endgroup\$
  • \$\begingroup\$ @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. \$\endgroup\$ – khateeb Nov 2 '14 at 2:14
  • 1
    \$\begingroup\$ Shuffling before sorting seems wasteful. You would be better off choosing a random element or the median of three elements as the pivot. \$\endgroup\$ – 200_success Nov 2 '14 at 2:26
  • \$\begingroup\$ Should my partition function be also inclusive-exclusive range? \$\endgroup\$ – khateeb Nov 2 '14 at 2:29
  • 1
    \$\begingroup\$ Yes, I would recommend consistently using inclusive-exclusive ranges everywhere. \$\endgroup\$ – 200_success Nov 2 '14 at 2:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.