Q1 Sorting with duplicates (30 marks)¶
The input is a unsorted list of non-negative real numbers. The list has size $n$, and there are $k \leq n$ different numbers in that list (i.e. there may be duplicates).
Q1.1 (25 marks)¶
Design and implement an algorithm which can sort this list and has average runtime in $O(n \log k)$. You may only use the Python $list$ container, and no other (so no dictionary, no set, etc). You may not use an existing implementation of a sorting algorithm (including Python’s). If you feel that it is needed, you can write your own implementation of a sorting algorithm. Any other data structure that you need has to be implemented here as well. For reference, the solution code is less than 40 lines long.
In [0]:
def sortlist(l):
“”” Returns a sorted list which contains the same elements as l
(including duplicates). The input list l should not be changed.”””
#TODO implement your algorithm here.
pass
We provide unit tests below. Your implementation must pass all tests to get full marks. For reference, the solution code runs in less than a minute. If your code requires a significant longer time to run, then it may be bugged, or your algorithm may not have an average runtime in $O(n \log k)$.
In [0]:
import unittest
import random
import math
random.seed(a=0)
class Testsortlist(unittest.TestCase):
def setUp(self):
self.numbers = [math.sqrt(i) for i in random.sample(range(10000000), 1000)]
self.ntests = 100
def checklist(self, l):
check = sortlist(l)
l.sort()
self.assertEqual(l, check)
def testEmpty(self):
self.checklist([])
def testSingle(self):
self.checklist([0])
def testNoMult(self):
for _ in range(self.ntests):
self.checklist(random.sample(self.numbers, len(self.numbers)//2))
def testkMult(self):
for k in [2, 5, 10, 100]:
for _ in range(self.ntests):
self.checklist(random.choices(self.numbers, k=k*len(self.numbers)))
In [0]:
testlist = Testsortlist()
suite = unittest.TestLoader().loadTestsFromModule(testlist)
unittest.TextTestRunner().run(suite)
Q1.2 (5 marks)¶
Prove that your algorithm has an average runtime in $O(n \log k)$. Determine and prove its worst-case runtime.
(write your answer here)