I can’t seem to get this done correctly. I’ve pasted my code below. Using the print statements, I think what’s happening is that the result of the first pass is what is being returned as the answer, although all the recursive steps show output via print that they’re working as intended, but it seems as though the result isn’t being saved? I was trying to do this in-place, which I tried to do but just modifying array[], but I feel as though I have some misconceptions here. Any help is appreciated.
Codepad: http://codepad.org/jVMbbJTq
Code:
def quicksort(array):
if len(array) >1:
print "enter array", array
pivot = len(array) - 1
print "pivot", array[pivot]
x = 0
while x < pivot:
if array[x]>array[pivot]:
piv = array[pivot]
xval = array[x]
array[x] = array[pivot-1]
array[pivot] = xval
array[pivot-1] = piv
# temp = array[x]
# array[x] = array[pivot]
# array[pivot] = temp
# array.append(array.pop(x))
pivot -= 1
else:
x += 1
print "pre recur split array", array
print "left", array[:pivot]
print "right", array[pivot+1:]
quicksort(array[:pivot])
quicksort(array[pivot+1:])
print "post recur split array", array
return array
test = [21, 4, 1, 3, 9, 20, 25, 6, 21, 14]
#test = [21, 4, 1, 3]
print quicksort(test)
print "answer", test
I'm not sure if it's the only problem with your code, but one big issue you have is that your recursion won't do anything useful. That is, these two lines do nothing for you:
quicksort(array[:pivot])
quicksort(array[pivot+1:])
The reason they do nothing is that the slice you do copies the data from the input list array into a new list. Then the recursive call tries to sort the copied list. The recursive sorting doesn't change the original list at all, so if you ignore their return values, nothing ends up changed in the calling code.
There are a few ways to fix the issue. A simple (but inefficient) fix would be to assign the value returned by each of the recursive calls back into a slice of original list:
array[:pivot] = quicksort(array[:pivot])
array[pivot+1:] = quicksort(array[pivot+1:])
If you're going to do something like that though, using temporary lists for the partitioning steps earlier in the code might make everything easier to understand (there's no reason to partition in-place if you're going to copy all the data anyway during the recursion).
Here's a really quick and dirty quicksort that copies things a bunch (and so it is not very efficient):
def quicksort(array):
if len(array) <= 1:
return array
pivot_val = array[-1]
lower = [x for x in array if x < pivot_val]
upper = [x for x in array if x > pivot_val]
pivot_count = array.count(pivot)
return quicksort(lower) + [pivot_val]*pivot_count + quicksort(upper)
A different, more efficient approach would be to avoid making any copies of the data (which means no slicing). Just sort everything in-place, including the recursive parts. For this to work, you'll need to be able to pass extra arguments in the recursive calls to specify which range of indexes need to be sorted. Fortunately, it's easy to add optional arguments to a function in Python (another option is to have a separate helper function that handles all the recursion).
This involves more changes to your code than the simple fix above, as you can no longer use len(array) as a guide to where the pivot should be found (or to tell when you're done recursing). Here's a quick attempt at it, but I may have an off by 1 error or some other mistakes that you'll need to debug:
def quicksort(array, low=0, high=None): # add optional arguments
if high == None:
high = len(array) - 1 # set high if it got the default
if high - low > 0:
pivot = high # use high and low to set up pivot and x
x = low
while x < pivot:
if array[x]>array[pivot]: # this part stays the same
piv = array[pivot]
xval = array[x]
array[x] = array[pivot-1]
array[pivot] = xval
array[pivot-1] = piv
pivot -= 1
else:
x += 1
quicksort(array, low, pivot-1) # pass on new high and low values
quicksort(array, pivot+1, high)
return array # you probably don't need this line any more
If you go for this in-place approach, you might want to get rid of the return array part of the function. The standard for Python functions that operate in place is to return None (which is what happens if you don't have any return statement). Many methods that you'll be familiar with work like this. For instance, list.append doesn't return anything, nor does list.sort (the "official" sorting function). Functions in standard library modules, like random.shuffle will also return None when the modify a list that you pass them.