# Quicksort in Python

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?

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.

• Great points, thanks! In regards to the unused variables in quicksort_pivot_select: I was originally was going to have it pick the median-of-three but I got lazy and changed my mind, and forgot to change the signature of it. About the variable names: what are some idiomatic names for that type of thing in Python? Because I know in C++ I would've called them something like input, first, and last. – chbaker0 Sep 19 '14 at 23:21
• Those all sound much better than l, b, and e. As for idiomatic python names, well, the rules are the same as C++ .... make your code as self-documenting as you can. And input, first, and last seem so much better. – rolfl Sep 19 '14 at 23:23

### 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.

• Thanks! I got rid of the bug, the line should've been left_div = b. Good point on the sorted vs quicksort thing, I didn't even know sorted was there (shows I have a lot more to learn in Python); quicksorted is certainly good middle ground. And, of course, I'll look over PEP8. It's good to know I'm starting out alright, thank you! – chbaker0 Sep 20 '14 at 6:41
• @mebob - janos raises excellent points. I would go so far as to suggest you accepted my answer too soon (feel free to change). Additionally, the bug he found is something I may have seen had 1) I actually ran your code (though that should not be needed), and 2) your variable names not been l and the bug because of 1. – rolfl Sep 22 '14 at 10:23