#so that all left <= pivot < all right,

#, and the partition will do all the inplace sort

def print_array(arr):

for a in arr:

print a,

def swap(a,index1, index2):

temp = a[index1]

a[index1] = a[index2]

a[index2] = temp

def partition(arr, left, right):

print "left:"+str(left)

print "right:"+str(right)

if right == left:

return -1

i = left - 1

j = left

pivot = arr[right]

while j < right:

if arr[j] > pivot:

j = j + 1

elif arr[j] <= pivot:

i = i + 1

swap(arr,i,j)

j = j + 1

print "swap (left,right):"+str(left)+","+str(right)

print "before swap"

print_array(arr)

swap(arr,i+1,right)

print "after swap" #weird bug! one more element here?

print_array(arr)

#now the povit has divided the array into two partition,

#: all left <= pivot < all right

#need to return the new right for the new left partition

if i == left-1: return left

else: return i

def quick_sort(arr, left, right):

middle = partition(arr,left,right)

print middle

if middle != -1:

print "after quick sort left"

quick_sort(arr,left,middle)

print "after quick sort right"

quick_sort(arr,middle+1,right)

if __name__ == "__main__":

array = [9,4,1,2,5,3,6,8,7,0]

quick_sort(array,0,9)

print_array(array)

## No comments:

Post a Comment