class Sort(object):
def quick_sort(self, ls):
self.quick_sort_helper(ls, 0, len(ls) - 1)
return ls
def quick_sort_helper(self, ls, start, end):
if end <= start:
return
pivot_index = random.randint(start, end)
pivot = ls[pivot_index] # pivot value
ls[pivot_index], ls[end] = ls[end], ls[pivot_index] # swap with the value in index end.
boundary = start # boundary is in index start.
for i in range(start, end):
if ls[i] < pivot:
ls[i], ls[boundary] = ls[boundary], ls[i] # swap with the value in index i.
boundary += 1
ls[boundary], ls[end] = ls[end], ls[boundary] # lie the pivot in index boundary.
self.quick_sort_helper(ls, start, boundary - 1)
self.quick_sort_helper(ls, boundary + 1, end)
def merge_sort(self, ls):
buffer = ls[:]
self.merge_sort_helper(ls, buffer, 0, len(ls) - 1)
return ls
def merge_sort_helper(self, ls, buffer, start, end):
if end <= start:
return
middle = (start + end) // 2
self.merge_sort_helper(ls, buffer, start, middle)
self.merge_sort_helper(ls, buffer, middle + 1, end)
i1, i2 = start, middle + 1
for i in range(start, end+1):
if i2 > end:
buffer[i] = ls[i1]
i1 += 1
elif i1 > middle:
buffer[i] = ls[i2]
i2 += 1
elif ls[i1] < ls[i2]:
buffer[i] = ls[i1]
i1 += 1
else:
buffer[i] = ls[i2]
i2 += 1
ls[start:end+1] = buffer[start:end+1]
if __name__ == '__main__':
ls = [1, 9, 5, 4, 3, 7, 6]
s = Sort()
print(s.quick_sort(ls[:]))
print(s.merge_sort(ls[:]))
