# Is this a proper quicksort algorithm in Python?

import random

def qsort(qslist):

small = []
big = []

if (len(qslist) < 2):
return qslist

elif (len(qslist) > 1):

pivot = qslist[int(random.randrange(len(qslist)))]

for x in range(len(qslist)):
if qslist[x] <= pivot:
small.append(qslist[x])
else:
big.append(qslist[x])
if(len(big) == 0):
big.append(pivot)
small.remove(pivot)

return qsort(small) + qsort(big)

qslist = [9,1,8,2,7,3,6,4,5]
print(qsort(qslist))


Please give me advice while picking up Python. I'm trying to do so while at the same time doing some basic algorithms.

1. Have I understood how the quicksort algorithm work?
2. Please give me some general feedback on the Python code.

• Write docstrings to document code
• Use if/else instead of if/elif if possible
• Use list comprehensions
• Use random.choice to get a random element from a non-empty sequence

The code in the original questions with the suggested improvements would be as follows:

import random

def qsort(qslist):
""""Quicksort implementation."""
if len(qslist) < 2:
return qslist

pivot = random.choice(qslist)
small = [x for x in qslist if x < pivot]
equal = [x for x in qslist if x == pivot]
big = [x for x in qslist if x > pivot]

return qsort(small) + equal + qsort(big)

qslist = [9,1,8,2,7,3,6,4,5]
print(qsort(qslist))


Edit: If you prefer to avoid traversing the array three times, a partition function to do that very similar to the one in the original question would be:

def partition(qslist):
"""Partition array using a pivot value."""
small = []
equal = []
big = []

pivot = random.choice(qslist)
for x in qslist:
if x < pivot:
small.append(x)
elif x == pivot:
equal.append(x)
else:
big.append(x)

return small, equal, big

• Hello, thanks for your reply, but i wonder if your code works if the list contains several of the "same" items, it dosent seem todo. Chane the list to contain several "1" to se what i mean. Commented Aug 6, 2014 at 10:52
• Thanks for your comment. The code indeed failed in the case of repeated values, I've updated it to take that into account. Commented Aug 6, 2014 at 10:59
• Great, i need to do a bit more of list compehensions! :) Commented Aug 6, 2014 at 11:11
• Note that I used list comprehensions for readability, but you can still define your own partition function to do just one pass over qsist which would be more efficient. Commented Aug 6, 2014 at 11:13
• @miR What I suggest is if/else over if/elif when the condition in the elif is exclusive and, hence, not needed. Commented Aug 7, 2014 at 7:27

A few comments, not so much about the algorithm as it has be done pretty well already but more about the code itself :

• your return does not seem properly indented.
• you should put your test (or basically any code actually doing something) behind a main guard.
• there is no point in checking if the length is bigger than 1 after you've checked that it is not smaller than 2. If you really want to, you can add an assert.
• you can (and should) define big and small as late as possible : we will only need them in the else case, this is where it belongs.
• the way you loop over the list is not pythonic at all. You should see the for loop as a for-each loop and use it as such. It makes things easier to read/write, it is shorter, it is more efficient and it will be easier to re-use if you have to work on different iterables.
• you could put your return in the else block or you could get rid of the else block alltogether as your return in the then block.

After taking into account these simple comments, here is what I have :

import random

def qsort(qslist):

if len(qslist) < 2:
return qslist

assert len(qslist) > 1
pivot = random.choice(qslist)

small = []
big = []

for x in qslist:
if x <= pivot:
small.append(x)
else:
big.append(x)
if len(big) == 0:
big.append(pivot)
small.remove(pivot)

return qsort(small) + qsort(big)

def main():
"""Main function"""
print("Hello, world!")
qslist = [9, 1, 8, 2, 7, 3, 6, 4, 5] * 200
print(qsort(qslist))

if __name__ == "__main__":
main()


Yes, the algorithm looks like quicksort.

There are only two things I would have done differently:

1. Why do you randomly generate a number within the range of the list to pick the corresponding element? Just randomly pick an element from the list:

pivot = random.choice(qslist)

2. Why do you generate sequential indices to pick all elements of your list? Just sequentially pick all elements: for value in qslist: ...