# Python implementation of quicksort

My teacher often tells me that I don't take full advantage of Python capabilities, I would like to know if my implementation of Quicksort is good enough and how could I improve it, aside from doing it in-place

def quickSort(l):
if len(l) > 1:
l,iPiv = partition(l)
return quickSort(l[:iPiv]) + [l[iPiv]] + quickSort(l[iPiv+1:])
else:
return l

def partition(l):
i = 1
iPiv = 0
for j in range(1,len(l)):
if l[j] <= l[iPiv]:
l[i],l[j] = l[j],l[i]
i += 1
l[i-1],l[iPiv] = l[iPiv],l[i-1]
return l,i-1

• You defined particionar(), but you call partition(). Please make up your mind? Nov 7, 2014 at 4:34
• Sorry, I translated it when posting, particionar was the spanish name of the function :P Nov 7, 2014 at 5:18

It looks quite nice, but I suggest renaming some variables and methods:

• Rename l to items, because l is just too short and hard to read
• Rename iPiv to pivot, because it's more readable
• Rename quickSort to quicksort because it's very widely known and used that way

To follow PEP8, put a space after comma in tuples, for example l, iPiv instead of l,iPiv

When you have this kind of code:

if cond:
# do something
return x
else:
# do something
return y


... you can drop the else and just use return y

The result:

def quicksort(items):
if not len(items) > 1:
return items
items, pivot = partition(items)
return quicksort(items[:pivot]) + [items[pivot]] + quicksort(items[pivot+1:])

def partition(items):
i = 1
pivot = 0
for j in range(1, len(items)):
if items[j] <= items[pivot]:
items[i], items[j] = items[j], items[i]
i += 1
items[i-1], items[pivot] = items[pivot], items[i-1]
return items, i-1

• I'm really thankful about your suggestions. Naming: that's my daily struggle! I chose your answer because it improved my existing code, and, while I love list comprehensions, they aren't available in all languages, as for parallel assignment, concatenation and splicing, python just gives you shortcuts, but the main logic can be applied elsewhere. Again, thank you Nov 9, 2014 at 23:30

My teacher often tells me that I don't take full advantage of Python capabilities

Try partitioning with list comprehensions.

import random

def quicksort(s):
len_s = len(s)
if len_s < 2:
return s

pivot = s[random.randrange(0, len_s)]

L = [x for x in s if x < pivot]
E = [x for x in s if x == pivot]
G = [x for x in s if x > pivot]

return quicksort(L) + E + quicksort(G)


This is Pythonic, compact and faster than your partition function.

Furthermore, notice the pivot is random. Your original code always uses zero for the pivot. This results in worst-case O(n^2) complexity for sorted inputs. A random pivot mitigates this risk.

As for style, the answer from @janos offers solid guidance also.

• Wow! that's a neat way to use list comprehensions! as for the random pivot, I'm aware of the issues about choosing always the first element as pivot, I just made it that way for simplicity, that's why I used the iPiv variable despite it being 0 everytime Nov 9, 2014 at 23:26