Week 8 Handout - MAS1803 Problem Solving with Python 2021-22
Dr Chris Graham 1
Handout 8
Let's start with a warning: this is the toughest week of content in the module. You'll want to move
through the content very slowly: there's nothing here that we haven't already seen, but it's
important to understand each and every line of code, or it will be very easy to get lost...
Introduction
This week's topic is sorting algorithms. In essence, how do we sort a list of numbers like
x = [4,6,1,2,10,8]
such that x becomes
[1,2,4,6,8,10]
See this week's lecture for why we're so interested in doing something that isn't just this...!
x.sort()
A couple of the key motivations:
that it's very easy to understand the task: to replicate this functionality; and
it's very easy to check our results.
Those were two of the key steps in our problem solving flowchart in week 6, so it just leaves us
the (not insignificant) task of coding up the algorithms!
Throughout the handout we will talk about sorting lists of integers. There's no reason why the
idea couldn't apply to other types of data though.
Categories of sorting algorithm
There are a number of different categories of sorting algorithm:
Selection Algorithms which pick out the smallest element, then the next smallest, and
so on
Exchange Swap elements which are out of sequence (e.g. bubble sort)
Insertion Sort like you would a deck of cards, trying to place each one in turn in the
correct place
Bucket/merging Divide and conquer type approaches (e.g. merge sort)
Often the categorisation of sorting algorithms is blurry, they can fall into more than one of the
above, they can be referred to with multiple names, have many variants, and you might find them
written with or without spaces, e.g. merge sort / mergesort. We won't be too concerned with
becoming all-knowing experts in this field (I certainly can't claim to be), rather we are going to
pick a small number of these algorithms, try to understand them and code them up.
Week 8 Handout - MAS1803 Problem Solving with Python 2021-22
Dr Chris Graham 2
Enumeration sort
In the lecture this week (see ReCap or the week 8 dashboard for a recording), we considered the
case of sorting a list of numbers by taking each element in the list and counting how many
others were smaller than it. We figured out that the number of comparisons required to carry this
out is .
Let's recap a couple of the key steps. If you were at the lecture and understood perfectly then
skip ahead to the section Full code for enumeration sort.
Our enumcount function
We first sought to create a function enumcount(x) which takes in a list x . The purpose of the
function was to return a list in which each element is a count of how many values come before
the respective elements in x. So our intention was that the following code
x = [4,6,1,2,10,8]
enumcount(x)
returns
[2, 3, 0, 1, 5, 4]
I.e. there are 2 values in the list that are less than 4, 3 less than 6, 0 values less than 1. Don't go
any further until you've got your head around this aim.
Inside our function we're first doing the following:
n = len(x)
c = [0 for i in range(n)]
the first line finds the length of x . The second creates an empty list of zeros. I'm doing this as
opposed to using np.zeros to avoid using NumPy (though it would work if we did so, we'd just
end up with a NumPy array and our code wouldn't be as easy to adapt for different data types).
Check how things are going with
print(c)
[0, 0, 0, 0, 0, 0]
So now things are a bit tricky, we need to loop through each element in x
for i in range(1,n):
and inside that we compare every value up to the value i (see my football fixtures analogy in the
lecture).
for i in range(1,n):
for j in range(0,i):
inside that we check to see what x value is larger, x[i] or x[j] and update the c[i] or
c[j] element accordingly:
1
2
n(n− 1)
Week 8 Handout - MAS1803 Problem Solving with Python 2021-22
Dr Chris Graham 3
for i in range(1,n):
for j in range(0,i):
if x[i] < x[j]:
c[j] = c[j]+1
else:
c[i] = c[i]+1
The whole thing looks like this:
def enumcount(x):
"""
Returns a list with a count of how many values
come before each element in x
"""
n = len(x)
c = [0 for i in range(n)]
for i in range(1,n):
for j in range(0,i):
if x[i] < x[j]:
c[j] = c[j]+1
else:
c[i] = c[i]+1
return c
Our enumsort function
The purpose of the enumsort function is to take in the original list x and the output from
enumcount and return a sorted list for x . So, for example
x = [4,6,1,2,10,8]
c = enumcount(x) # equal to [2, 3, 0, 1, 5, 4]
enumsort(x,c)
would return
[1, 2, 4, 6, 8, 10]
In the function, again we find the length of x and initialise a new list xsorted to put our sorted
values in.
n = len(x)
xsorted = [0 for i in range(n)]
We then loop through each value placing the ith x value into position c[i]
for i in range(n):
xsorted[c[i]] = x[i]
Here's the function in full, with an additional error handling to check that x and c are the same
length (otherwise something has gone terribly wrong):
Week 8 Handout - MAS1803 Problem Solving with Python 2021-22
Dr Chris Graham 4
def enumsort(x,c):
"""
returns a sorted list, given x, the original list
and c, the output of enumcount(x)
"""
if(len(x)!=len(c)):
raise ValueError('c and x should be same length')

n = len(x)
xsorted = [0 for i in range(n)]
for i in range(n):
xsorted[c[i]] = x[i]

return xsorted
Full code for enumeration sort
def enumcount(x):
"""
Returns a list with a count of how many values
come before each element in x
"""
n = len(x)
c = [0 for i in range(n)]
for i in range(1,n):
for j in range(0,i):
if x[i] < x[j]:
c[j] = c[j]+1
else:
c[i] = c[i]+1
return c
def enumsort(x,c):
if(len(x)!=len(c)):
raise ValueError('c and x should be same length')

n = len(x)
xsorted = [0 for i in range(n)]
for i in range(n):
xsorted[c[i]] = x[i]

return xsorted
Note that [0 for i in range(n)] creates a list of n zeros, just like NumPy's zero . I'm trying
not to use any additional modules inside the actual functions.
Week 8 Handout - MAS1803 Problem Solving with Python 2021-22
Dr Chris Graham 5
Exercise 8.1
Let's have a try out of the algorithm and do some timing:
Show Exercise
Bubble Sort
Bubble sort is a type of exchange sort, where out-of-sequence elements are swapped. It requires
a bit more bookkeeping than the enumeration sort, to make sure that only the necessary
comparisons are made.
Understanding bubble sort
The basic idea is as follows:
Compare the first pair of elements. If the first is greater than the second, swap them. Repeat for
the next pair and so on, until all numbers are in order. This may involve starting again at the
beginning when necessary, and moving entirely from left to right is referred to as a pass through
the list.
During each pass through the list, the highest unsorted number is guaranteed to move to the end
of the unsorted numbers.
The concept is relatively straightforward: keep passing through the list swapping elements that
are not in order. Each pass is at least one comparison shorter than the previous one.
For other illustrations of the bubble sort algorithm, see the resources page (link at the top of this
one).
Bubble sort algorithm
The bubble sort algorithm is longer than our enumeration sort algorithm, because we want to
keep track of which values are already in the right place.
Here's an algorithm for bubble sort, read it very carefully, then I'll add a bit more explanation
Week 8 Handout - MAS1803 Problem Solving with Python 2021-22
Dr Chris Graham 6
Input the list x to be sorted and find length n

let bound = n - 1 {the highest element not known to be in the correct
position}

while bound > 0 {whilst not everything is in order}
swap = 0 {there have been no swaps yet}
j = 1 {initialise j, which will be the index of elements}
for j < bound
if x[j] > x[j + 1] {then they are in the wrong order}
exchange elements x[j] and x[j+1]
swap = j {identifies the last pair that were swapped in this
pass}

bound = swap
{if bound is greater than 0 then we start a new pass}

Output the sorted list x
If a pass through x produces no swaps, then swap = 0 at the end of the inner loop, at this point
we can exit from the outer while loop and return the sorted list. If swap is greater than zero then
we need at least one more pass.
The value of swap when the inner loop finishes identifies the last pair of elements that were
exchanged; everything after and including this pair is already in the correct order and does not
need to be tested again. The variable bound will mark the boundary between sorted and
unsorted numbers, so it will start at n-1 and move towards 0 as the list is sorted.
Code for bubble sort
Note that we can swap element j and j+1 of x like this
x[j], x[j+1] = x[j+1], x[j]
But actually, though this takes more lines, it's clearer and appears to be slightly faster to do
tmp = x[j+1]
x[j+1] = x[j]
x[j] = tmp
OK, here we go:
Week 8 Handout - MAS1803 Problem Solving with Python 2021-22
Dr Chris Graham 7
def bubble_sort(x):

n = len(x)
# records position of the last element not known to be in the correct
position
bound = n-1
while bound > 0:
# records if/where swap took place
swap=0

# step through elements of x not known to be in the correct place
for j in range(0, bound):

# if x[j] is bigger then swap
if x[j] > x[j+1]:
tmp = x[j+1]
x[j+1] = x[j]
x[j] = tmp
swap = j

bound = swap

return x
Exercise 8.2
Some things to try out:
Show exercise >
Some thoughts on bubble sort
Its an interesting algorithm, because it's not too complicated, however the performance of
bubble sort scales with n no better than our enumeration algorithm (still - try out your
previous timing code and you will still get something like a quadratic, eventually)$. Where it does
have applications is, for example, lists where just a couple of elements are out of order, for which
it is very fast.
Those poor lego guys are still working hard though... let's now look at an algorithm which scales
much better with n .
O(n
2
)
Week 8 Handout - MAS1803 Problem Solving with Python 2021-22
Dr Chris Graham 8
Merge sort
Merge sort uses a "divide and conquer" strategy; break the list down into smaller components,
sort the components and merge them. Merge sort also illustrates an important and
sophisticated property of algorithms: recursion. Recursive algorithms use themselves.
Understanding merge sort
The idea is to sort a list that we split it into two parts, sort each part and merge them in
ascending order. The parts are each sorted using the same algorithm.
The following animation demonstrates the idea behind the splitting / merging and recursion:
Merge sort algorithm
We actually require two algorithms (or functions) to implement merge sort:
First, an algorithm that will merge two lists, which are already sorted, into a single sorted list.
Second, a recursive algorithm that does the following: It first splits the intial list into two
parts and then calls itself to split each of the two parts into two other parts and so on, until
the parts can be split no more. It then uses the merge algorithm (the first algorithm) to
combine parts repeatedly, until there are no more parts to merge.
The merging reverses the sequence of splitting: as each split is reversed the elements are put
back together but now in ascending order. This second algorithm sounds complicated, because
the concept of recursion is unusual, but it is actually very short and simple to implement.
Merge function
The following algorithm will merge two sorted lists, x and y, into a sorted list z. I've laid it out in
pseudocode here.
Lego Bubble Sort
Week 8 Handout - MAS1803 Problem Solving with Python 2021-22
Dr Chris Graham 9
read in lists x and y

initialise a list z to store the sorted values

set counters for x,y and z
i = j = k = 0

while i less than len(x) and j less than len(y)
check if x[i] < y[j]:
z[k] = x[i]
move i along by 1
else:
z[k] = y[j]
move j along by 1
move k along by 1

At this point we've exhausted one of the two lists
fill z with any remaining values
while i < len(x)
add x[i] to z
while j < len(y)
add y[j] to z

return z
Exercise 8.3
I've put a lot of "code" into the above pseudocode. Let's have a go at going from here to actual
code.
Show Exercise
Merge sort function
Now we use the above recursively to implement the merge sort algorithm. The merge function is
used by the following function that sorts an input list x into ascending order. This function calls
itself recursively, until the test if len(x)>1 is no longer true for all of the parts, i.e. each part is
a single number.
Then it starts merging the parts; each merge reverses an earlier split but now the elements are
put into ascending order. The sequence of merging is the reverse of the sequence of splitting.
I've put this part straight into code for you:
Week 8 Handout - MAS1803 Problem Solving with Python 2021-22
Dr Chris Graham 10
def merge_sort(x):

if len(x)>1:
mid = round(len(x)/2)
l = x[:mid]
r = x[mid:]

# Sort the left and right sides
xl = merge_sort(l)
xr = merge_sort(r)

else:
return x

return merge(xl,xr)
Now the merge sort function can be called for some list x
merge_sort(x)
More algorithms
There are a lot of other sorting algorithms and we've barely scratched the surface here. If you've
enjoyed tackling these then you may like to check out others. There also some excellent
resources and interesting things to find. For example this video has captured the sound of
several sorting algorithms at work. It's quite amusing and gives a visualisation of the approaches
algorithms take.
Visualgo is another good resource: an interactive website in which you can play around with
sorting algorithms.
And for some really out there stuff, check out this group of dancers performing bubble sort
(more on the AlgoRythmics Youtube channel)
15 Sorting Algorithms in 6 Minutes
Week 8 Handout - MAS1803 Problem Solving with Python 2021-22
Dr Chris Graham 11
Every year I do a Google to see what weird and wonderful videos are out there, and this guy
commentating as he simulates a race between 7 different sorting algorithms in the "Sorting
Algorithm Olympics" is really up there, complete with slow motion action replays of the races!
Bubble-sort with Hungarian ("Csángó") folk dance
The Sorting Algorithm Olympics - Who is the Fastest of the…

欢迎咨询51作业君