HiveBrain v1.2.0
Get Started
← Back to all entries
snippetpythonMinor

Python implementation of quicksort

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
implementationpythonquicksort

Problem

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

Solution

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

Code Snippets

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)

Context

StackExchange Code Review Q#69133, answer score: 8

Revisions (0)

No revisions yet.