Search This Blog

Thursday, June 11, 2009

Python Quick Sort

#the purpose of povit is to divide the array into two partition,
#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
j = j + 1

print "swap (left,right):"+str(left)+","+str(right)
print "before swap"
print "after swap" #weird bug! one more element here?

#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"
print "after quick sort right"

if __name__ == "__main__":
array = [9,4,1,2,5,3,6,8,7,0]

No comments: