11
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ You defined particionar(), but you call partition(). Please make up your mind? \$\endgroup\$ – 200_success Nov 7 '14 at 4:34
  • 1
    \$\begingroup\$ Sorry, I translated it when posting, particionar was the spanish name of the function :P \$\endgroup\$ – davidaam Nov 7 '14 at 5:18
4
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – davidaam Nov 9 '14 at 23:30
8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – davidaam Nov 9 '14 at 23:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.