quicksort and recursion in python

Question

I'm trying to implement quicksort in Python using 2 main functions - partition and quicksort. The partition function is designed so that it returns 2 arrays - bigger and smaller than p. after that quicksort is called on both of them separately. so the quicksort works like this:

def quicksort(array)
    pivot = 0 # pivot choice is irrelevant
    left,right = partition(array,pivot)
    quicksort(left)
    quicksoft(right)
    return left+right

But from my understanding it should be possible to design partition to return just one single index - delimiting bigger and smaller arrays and redesign quicksort as follows:

def quicksort(array)
    pivot = 0 # pivot choice is irrelevant
    i = partition(array,pivot)
    quicksort(array[:i-1])
    quicksoft(array[i:])
    return array

but this implementation returns partially sorted array

original array [5, 4, 2, 1, 6, 7, 3, 8, 9]
sorted array [3, 4, 2, 1, 5, 7, 6, 8, 9]

what am i missing here?

Are you confident your new partition() function modifies the array in place? — sarnold
– sarnold, Commented Mar 26, 2012 at 0:55
I wrote a very similar partition function stackoverflow.com/a/9244923/632088 which uses hi - low indices instead of copying lists everywhere. Hope it might help — Rusty Rob
– Rusty Rob, Commented Mar 26, 2012 at 1:03
As a general rule: if function modifies its argument inplace it should return None e.g., L.sort() vs. sorted(L). — jfs
– jfs, Commented Mar 26, 2012 at 1:04

andrew cooke · Accepted Answer · 2012-03-26 00:59:44Z

4

without seeing your code it's hard to be sure, but one possible error is the i-1:

>>> [1,2,3,4][:2]
[1, 2]
>>> [1,2,3,4][2:]
[3, 4]

(although you may be simply skipping the pivot?)

also, slices are new lists, not views:

>>> l = [1,2,3,4]
>>> l[2:][0] = 'three'
>>> l
[1, 2, 3, 4]

which is unfortunate (the typical functional program doing quicksort which is not a quicksort at all, dammit, because it's creating a pile of new arrays annoys me too...)

you can work round the second problem by passing the entire list plus lo/hi indices:

def quicksort(data, lo=0, hi=None):
    if hi is None: hi = len(data)
    ....

edited Mar 26, 2012 at 0:59

answered Mar 26, 2012 at 0:53

andrew cooke

47.1k10 gold badges102 silver badges148 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

JiBB · Accepted Answer · 2012-03-26 01:37:25Z

1

quicksort(array[:i-1]) doesn't actually call quicksort on the first partition of the array, it calls quicksort on a copy of the first partition of the array. Thus, your code is partitioning the array in place, then creating copies of the halves and trying to sort them (but never doing anything with the resulting arrays), so your recursive calls have no effect.

If you want to do it like this, you'll have to avoid making copies of the list with slicing, and instead pass around the whole list as well as the ranges you want your functions to apply to.

answered Mar 26, 2012 at 1:37

JiBB

2513 silver badges2 bronze badges

Comments

Rob Berkes · Accepted Answer · 2013-01-15 21:30:10Z

0

I had the same problem, my quicksort was returning partially sorted lists. I found the problem was that I wasn't returning the pivot in it's own array. When I create an array for the pivot, it allows the recursion to work properly.

ie. my partition function returns instead of:

return left, right

it returns

return left, pivotval, right

answered Jan 15, 2013 at 21:30

Rob Berkes

862 bronze badges

Collectives™ on Stack Overflow

quicksort and recursion in python

3 Answers 3

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related