Quicksort in Python

Question

This is my first actual attempt at writing a Python program. I have a background in C++, so it was a big change (where's my iterators?), and I'm looking for criticism on my use of Python and its idioms. Here it is:

def quicksort_pivot_select(l, b, e):
    return b + (e - b) // 2

def quicksort_partition(l, b, e):
    pivot_index = quicksort_pivot_select(l, b, e)
    l[pivot_index], l[e-1] = l[e-1], l[pivot_index]

    left_div = 1
    right_div = e-1

    while left_div < right_div:
        if l[left_div] < l[e-1]:
            left_div += 1
        else:
            right_div -= 1
            l[left_div], l[right_div] = l[right_div], l[left_div]

    l[left_div], l[e-1] = l[e-1], l[left_div]

    return left_div

def quicksort_impl(l, b, e):
    if e - b <= 1:
        return

    part = quicksort_partition(l, b, e)

    quicksort_impl(l, b, part)
    quicksort_impl(l, part+1, e)

def quicksort(l):
    quicksort_impl(l, 0, len(l))

Any suggestions for improvement, like using existing language facilities I missed?

Answer 1

There are a number of good things, but also some bad ones in here.

Good

• you are using the correct 'find-the-mid-point' algorithm (b + (e - b) // 2), and this is commonly recommended to avoid an overflow bug, BUT, Python is not vulnerable to this bug. Python will extend the integer space to arbitrary precision to accommodate integers as big as you have memory to store. So, I am uncertain whether the non-obvious bug-killing option is a good choice here. I will leave it to you to decide....
• your functional extraction looks good, the logic blocks are clear, and it's more readable than some implementations which put all the logic in one place.

Not so good

• The regular swaps you do are fine, but I feel that they just look like code blocks, and I had a problem reading them. In general, I found you put spaces around operators, but in the swaps you compressed everything for some reason:

  l[left_div], l[e-1] = l[e-1], l[left_div]
  

  Now, you know how to use spaces around the - sign in expressions like:

  return b + (e - b) // 2
  

  So, by compressing the space in the swaps, it looks more like names, than expressions, e-1, especially when you use snake_case for other variables like left_div.

   l[left_div], l[e - 1] = l[e - 1], l[left_div]
  

  You also ran in to this problem any time you did a -1 index on a variable... it's inconsistent, and makes the code hard to read.

  Out of interest, you did a function-extraction for the calculating the mid-point... did you consider extracting the swap in to a function as well? It will improve readability, but I am uncertain of the performance impact. You call the swap multiple times, so it would add up faster than the mid-point.

• You have unused variables called in to the pivot-select function:

  def quicksort_pivot_select(l, b, e):
      return b + (e - b) // 2
  

  The l is not used, and should be removed.

• talking about l .... what's with that as a variable name? You show in your code that you can use decent variable names, so why do you have l, b, and e? The sometimes-good variables make these variable names even more painful. Combined with the regular use of the constant 1, it is a rookie mistake.

Overall

The overall implementation is probably much better than it looks. The readability issues detract from what looks like it would otherwise be an advanced implementation of the sort. The way you partition the data is clever, and efficient with the looping. In this case though, I would say that your presentation lets you down.

Answer 2

You have a bug

Try this:

items = [14, 3, 9, 2, 1, 5, 4, 2, 1, 3]
quicksort(items)
print(items)

It gives:

[14, 1, 1, 2, 2, 3, 3, 4, 5, 9]

In quicksort_partition, left_div = 1 looked suspicious, if I change that to left_div = 0, then it seems to be better:

[1, 1, 2, 2, 3, 3, 4, 5, 9, 14]

But not good enough. If you try with items = [14, 13, 9, 2, 1, 5, 4, 2, 1, 3] (change the first 3 to 13), you will get RuntimeError: maximum recursion depth exceeded. You need to debug this.

Naming

I propose these renames:

• l to items
• s to start, naturally
• e to end, naturally
• left_div to left, ldiv, or leave as is
• right_div to right, rdiv, or leave as is

This is a matter of taste though. input is not a good name for l because it's too generic and says nothing about what it is, but even more importantly, a built-in function with that name exists in Python 3.

Returning a sorted list

The built-in function sorted doesn't mutate the input list, it returns a new sorted list. You edit in-place, which is space efficient, and can be acceptable. However, the fact that you don't return the list makes it slightly more tedious to test. It would be easier if the function returned the sorted list. But that's really a good option, because then users might mistakenly believe that you don't mutate input list. Mirroring sorted, a good middle ground might be adding a helper called quicksorted:

def quicksorted(items):
    newitems = items[:]
    quicksort(newitems)
    return newitems

PEP8

Since you're new to Python, let me point out PEP8, the official Python coding style guide. Your code mostly passes (with flying colors), the only violation is that you should put 2 blank lines before each function definition. Overall, you're doing great, this just FYI.