# This function is for testing, do not modify
def check(actual, expected):
if expected != actual:
print(
f"Function should return the value {expected}, it is returning the value {actual}")
else:
print(f"Congratulations, the test case passed!")
Python3 has a built in sorting function that we can use for parts of this exercise.
Write a function sort4
that sorts a list of 4 elements. The function should make two calls to sort2
where sort2
sorts a list of size 2.
sort2 = sorted
def sort4(L):
L_first_sorted = sort2(L[0:2])
L_last_sorted = sort2(L[2:4])
#
# do something to return a sorted list
#
L = [5, 2, 1, 6]
check(sort4(L), [1, 2, 5, 6])
M = [4, 3, 2, 1]
check(sort4(L), [1, 2, 3, 4])
Write a function sort32
that sorts a list of 32 elements. The function should make two recursive calls to a provided function sort16
sort16 = sorted
def sort32(L):
L_first_sorted = sort16(L[0:16])
L_last_sorted = sort16(L[16:32])
#
# do something to return a sorted list
#
# TEST_CASE
L = [32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18,
17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
check(sort32(L), [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
18, 19, 20, 21, 22, 23, 24, 25,S 26, 27, 28, 29, 30, 31, 32])
Write a function merge_sort
that will sort a list of any size. The function should make two recursive calls to itself
def merge_sort(L):
#
# do something here
#
L_first_sorted = merge_sort(
L[0:int(len(L)/2)])
L_last_sorted = merge_sort(
L[int(len(L)/2):len(L)])
#
# do something to return a sorted list
L = [23, 10, 5, 1, 4]
check(merge_sort(L), [1, 4, 5, 10, 23])
M = [4, 3, 2, 1]
check(merge_sort(M), [1, 2, 3, 4])
Sort by hand using the quicksort method the following list of numbers {4,7,8,10,1,2,5,9,3,6} showing all your steps. Use the following pivots 7, 2, 9, 4.
Write your answer here:
Using quicksort, sort the following list of football teams based on their names. Try to write your own quicksort function based on the algorithm given in the lecture (below)
Algorithm Quicksort: Input L
of length n
.
Pick random j
in [0,...,n-1]
Let x=L[j]
and reorder L
so that locations L[0],..,L[j-1]
are smaller than x
and locations L[j],...,L[n-1]
are at least as large as x
.
Recursively sort L[0],...,L[j-1]
and L[j+1],...,L[n-1]
import random
L = ["Man United", "Leicester", "Chelsea", "Tottenham", "Arsenal",
"Liverpool", "Southampton", "Man City", "Crystal Palace"]
# Write your solution here:
Using your quicksort algorithm, sort the following list of football teams based on their points.
L = [["Man United", 10],
["Leicester", 3],
["Chelsea", 6],
["Tottenham", 5],
["Arsenal", 7],
["Liverpool", 9],
["Southampton", 1],
["Man City", 10],
["Crystal Palace", 9]]
# Write your solution here: