current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 7 down vote favorite

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

3 Answers 3

up vote 2 down vote accepted

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
share|improve this answer
    
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 –  davidaam Nov 9 '14 at 23:30
up vote -1 down vote

Try this traditional implementation:

def quicksort( aList ):
    _quicksort( aList, 0, len( aList ) - 1 )
 
def _quicksort( aList, first, last ):
    if first < last:
      pivot = partition( aList, first, last )
      _quicksort( aList, first, pivot - 1 )
      _quicksort( aList, pivot + 1, last )
 
 
def partition( aList, first, last ) :
    pivot = first + random.randrange( last - first + 1 )
    swap( aList, pivot, last )
    for i in range( first, last ):
      if aList[i] <= aList[last]:
        swap( aList, i, first )
        first += 1
 
    swap( aList, first, last )
    return first
 
 
def swap( A, x, y ):
  tmp = A[x]
  A[x] = A[y]
  A[y] = tmp
share|improve this answer

We're looking for long answers that provide some explanation and context. Don't just give a one-line answer; explain why your answer is right, ideally with citations. Answers that don't include explanations may be removed.
    
Welcome to Code Review! As it stands this answer looks more like your own solution to the OP's problem, than an actual review of their code - as such, it's not exactly the kind of answer we're expecting on this site. Feel free to post your solution as a new question if you'd like it reviewed :) –  Mat's Mug Dec 1 '14 at 16:36
up vote 3 down vote

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.

share|improve this answer
    
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 –  davidaam Nov 9 '14 at 23:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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