I have implemented this quicksort but I seem to have bug that I can not fix, would someone mind taking a quick look at it?
The output for the example I give is close to the answer but some indices are misplaced.
def partition(array, pivot, start, end):
# move pivot to the end
temp = array[pivot]
array[pivot] = array[end]
array[end] = temp
i = start
j = end - 1
while(i < j):
# check from left for element bigger than pivot
while(i < j and array[end] > array[i]):
i = i + 1
# check from right for element smaller than pivot
while(i < j and array[end] < array[j]):
j = j - 1
# if we find a pair of misplaced elements swap them
if(i < j):
temp = array[i]
array[i] = array[j]
array[j] = temp
# move pivot element to its position
temp = array[i]
array[i] = array[end]
array[end] = temp
# return pivot position
return i
def quicksort_helper(array, start, end):
if(start < end):
pivot = (start + end) / 2
r = partition(array, pivot, start, end)
quicksort_helper(array, start, r - 1)
quicksort_helper(array, r + 1, end)
def quicksort(array):
quicksort_helper(array, 0, len(array) - 1)
array = [6, 0, 5, 1, 3, 4, -1, 10, 2, 7, 8, 9]
quicksort(array)
print array
I have a feeling the answer will be obvious but I can not find it.
Desired output:
[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Actual output:
[-1, 0, 2, 3, 1, 4, 5, 6, 7, 8, 9, 10]
The critical repair is in the inner while loops, where you march i and j toward each other. If all you're worried about is swapping the correct non-pivot elements, the logic you posted is fine. However, that first loop needs to be
while(i <= j and array[end] > array[i]):
i = i + 1
to ensure that i has the correct value for swapping the pivot element into the middle. Otherwise, you can swap it one element to the left of its proper position, which is why your sort fails.
You can also use Python's multiple assignment for a cleaner swap:
while(i < j):
# check from left for element bigger than pivot
while(i <= j and array[end] > array[i]):
i = i + 1
# check from right for element smaller than pivot
while(i < j and array[end] < array[j]):
j = j - 1
# if we find a pair of misplaced elements swap them
if(i < j):
array[i], array[j] = array[j], array[i]
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments