8.2. Labelling lines

Assessed Coursework 2, Week 8

Part A: Sorting

The code in section 8.3 below (also available on Minerva) implements the merge sort

algorithm, you may use this in your work.

(1) Use perf_count and the other ideas from 8.1 above to generate a list of data, where

the ith entry is the time t, (i) necessary for merge-sort to sort lists of randomly chosen

elements of length 2¹ for i = 1, ..., 10.

(2) Plot tm (i) against 2¹ on a loglog plot. Briefly explain (as a comment) what the graph

says about merge-sort's speed, using big-O notation.

(3) Write a function insertionsort (somelist) that applies the insertion sort

algorithm described in lectures to sort a list. (You should use the pop and insert

commands as described in the lecture notes.)

(4) Use this to find the times tr(?) for lists of the same length as in (1). Add ty(i) to your

graph (on the same axes as above), and write a comment on what this says about the

speed of insertion sort, in big O notation.

(5) Write a function bubblesort (mylist) which implements Bubblesort, based on the

pseudocode described in lectures.

(6) Use this to find the times t(i) for lists of the same length as in (1). Add t (i) to your

graph (on the same axes as above), and write a comment on-what this says about the

speed of Bubblesort, in big O notation.

(7) Bubblesort has one advantage over quicker algorithms. If given an already sorted list

as input, Bubblesort can have complexity O(n) if it has a method of checking whether

any swaps occurred during one whole pass through the list. Write a new function

bubblesortsorted (mylist) which implements Bubblesort, but with the added

feature that checks this, and returns the sorted list immediately if no swaps occur during

the first complete pass through the list.