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\$
3
  • \$\begingroup\$ Where are isSorted and isSortedArray? \$\endgroup\$
    – jonrsharpe
    Nov 1, 2014 at 9:01
  • 1
    \$\begingroup\$ @jonrsharpe I don't think that the implementation of those functions is essential to the question. \$\endgroup\$ Nov 1, 2014 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, 2014 at 2:02

1 Answer 1

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\$
4
  • \$\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, 2014 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\$ Nov 2, 2014 at 2:26
  • \$\begingroup\$ Should my partition function be also inclusive-exclusive range? \$\endgroup\$
    – khateeb
    Nov 2, 2014 at 2:29
  • 1
    \$\begingroup\$ Yes, I would recommend consistently using inclusive-exclusive ranges everywhere. \$\endgroup\$ Nov 2, 2014 at 2:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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