quick_sort.py

importrandom


classQuickSort(object):
def__init__(self, numbers):
self.values=numbers
self.count=len(self.values)

defsort(self):
self.quick_sort(0, self.count-1)
returnself.values

defquick_sort(self, left, right):
ifleft==right:
return

i=left
j=right

pivot_index=random.randint(left, right)

pivot=self.values[pivot_index]

whilei<j:
whileself.values[i] <pivot:
i+=1
whileself.values[j] >pivot:
j-=1
ifi<=j:
temp=self.values[i]
self.values[i] =self.values[j]
self.values[j] =temp
i+=1
j-=1

ifleft<j:
self.quick_sort(left, j)
ifright>i:
self.quick_sort(i, right)