import random
def quicksort(mylist, first, last):
if first < last:
pivot = partition(mylist, first, last)
quicksort(mylist, first, pivot - 1)
quicksort(mylist, pivot + 1, last)
def partition(mylist, first, last):
# TODO: call get_pivot to get the pivot index
mylist[last], mylist[pivot_index] = mylist[pivot_index], mylist[last]
i = first
while i < last:
if mylist[i] <= mylist[last]:
mylist[i], mylist[first] = mylist[first], mylist[i]
first += 1
i += 1
mylist[first], mylist[last] = mylist[last], mylist[first]
return first
def get_pivot(mylist, first, last):
# TODO: randomly get three indices and assign the one with median value as pivot index
# TODO: return the pivot index.
a_list = [45, 31, 5, 12, 8, 67, 9, 20, 22]
print(a_list)
quicksort(a_list, 0, len(a_list) - 1)
print(a_list)