Python implementation of quicksort

Question

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

Answer 1

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

Answer 2

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.