Starter Code:

def find_zero(L): pass

def bubble(L, left, right): pass

def selection(L, left, right): pass

def insertion(L, left, right): pass

def sort_halfsorted(L, sort):

'''Efficiently sorts a list comprising a series of negative items, a single 0, and a series of positive items

Input

-----

* L:list

a half sorted list, e.g. [-2, -1, -3, 0, 4, 3, 7, 9, 14]

* sort: func(L:list, left:int, right:int)

a function that sorts the sublist L[left:right] in-place

note that we use python convention here: L[left:right] includes left but not right

Output

------

* None

this algorithm sorts `L` in-place, so it does not need a return statement

Examples

--------

>>> L = [-1, -2, -3, 0, 3, 2, 1]

>>> sort_halfsorted(L, bubble)

>>> print(L)

[-3, -2, -1, 0, 1, 2, 3]

'''

idx_zero = find_zero(L) # find the 0 index

sort(L, 0, idx_zero) # sort left half

sort(L, idx_zero+1, len(L)) # sort right half

Mod 6 Homework - Quadratic Sorts We will use "half sorted" to describe a list consisting of a series of negative integers, followed by a 0 , followed by a series of positive integers: We have provided an algorithm sort_halfsorted() that efficiently sorts such a list: \( \begin{array}{rlr}\text { def } & \text { sort_halfsorted(L, sort): } & \\ & \text { idx_zero = find_zero(L) } & \text { \# find the } 0 \text { index } \\ & \text { sort(L, 0, idx_zero) } & \text { \# sort left half } \\ & \operatorname{sort}(\mathrm{L}, \text { idx_zero+1, len(L)) \# sort right half }\end{array} \) It is up to you to implement the following algorithms such that sort_halfsorted works as expected: - find_zero(L) - return the index of the 0 in such a list in O(log(n)) - bubble(L, left, right), selection(...), and insertion(...) - sort the sub-list L [left:right] using the appropriate sorting algorithm - sort the list in-place (do not return anything) - bubble and insertion should be adaptive (O(n) in the best case ) - Follow Python convention - L [left:right] includes L [left] but not L [right]