Sign InCoursewareNuggetsTutorials AboutClassesCodePad

Randomized Quicksort

Implement function get_pivot by returning the index with the median value of three randomly chosen elements. By the median, we mean the element of the three whose value is in the middle.

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)
© CS Wonders·About·Classes·Cheatsheet