tarter 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] <---neg---> <----pos-----> * 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
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]
<---neg---> <----pos----->
* 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
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
Step by step
Solved in 3 steps with 3 images