Sorting exercises



In [ ]:

    
# Provided simple test() function used in main() to print
# what each function returns vs. what it's supposed to return.
def test(got, expected):
    if got == expected:
        prefix = ' OK '
    else:
        prefix = '  X '
    print '%s got: %s expected: %s' % (prefix, repr(got), repr(expected))

Fill in the code for the functions below. main() is already set up to call the functions with a few different inputs, printing 'OK' when each function is correct. The starter code for each function includes a 'return' which is just a placeholder for your code.

A. front_x

Given a list of strings, return a list with the strings in sorted order, except group all the strings that begin with 'x' first.

e.g. ['mix', 'xyz', 'apple', 'xanadu', 'aardvark'] yields ['xanadu', 'xyz', 'aardvark', 'apple', 'mix']



In [ ]:

    
def front_x(words):
    # +++your code here+++
    return



In [ ]:

    
test(front_x(['bbb', 'ccc', 'axx', 'xzz', 'xaa']),
   ['xaa', 'xzz', 'axx', 'bbb', 'ccc'])
test(front_x(['ccc', 'bbb', 'aaa', 'xcc', 'xaa']),
   ['xaa', 'xcc', 'aaa', 'bbb', 'ccc'])
test(front_x(['mix', 'xyz', 'apple', 'xanadu', 'aardvark']),
   ['xanadu', 'xyz', 'aardvark', 'apple', 'mix'])

B. sort_last

Given a list of non-empty tuples, return a list sorted in increasing order by the last element in each tuple.

e.g. [(1, 7), (1, 3), (3, 4, 5), (2, 2)] yields [(2, 2), (1, 3), (3, 4, 5), (1, 7)]



In [ ]:

    
def sort_last(tuples):
    # +++your code here+++
    return



In [ ]:

    
test(sort_last([(1, 3), (3, 2), (2, 1)]),
   [(2, 1), (3, 2), (1, 3)])
test(sort_last([(2, 3), (1, 2), (3, 1)]),
   [(3, 1), (1, 2), (2, 3)])
test(sort_last([(1, 7), (1, 3), (3, 4, 5), (2, 2)]),
   [(2, 2), (1, 3), (3, 4, 5), (1, 7)])

C. linear_merge

Given two lists sorted in increasing order, create and return a merged list of all the elements in sorted order. You may modify the passed in lists. Ideally, the solution should work in "linear" time, making a single pass of both lists.



In [ ]:

    
def linear_merge(list1, list2):
    # +++your code here+++
    return



In [ ]:

    
test(linear_merge(['aa', 'xx', 'zz'], ['bb', 'cc']),
   ['aa', 'bb', 'cc', 'xx', 'zz'])
test(linear_merge(['aa', 'xx'], ['bb', 'cc', 'zz']),
   ['aa', 'bb', 'cc', 'xx', 'zz'])
test(linear_merge(['aa', 'aa'], ['aa', 'bb', 'bb']),
   ['aa', 'aa', 'aa', 'bb', 'bb'])



In [ ]:

Note: This notebook is an adaption of Google's python tutorial https://developers.google.com/edu/python



In [ ]: