Is this a proper quicksort algorithm in Python?

Question

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.

Answer 1

Some comments:

• 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

Answer 2

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()

Answer 3

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