Exercise N - Visualising sorting algorithms
Contents
Exercise N - Visualising sorting algorithms¶
Andrew Valentine - andrew.valentine@anu.edu.au
We have already seen that Python provides various ‘sorting’ functions, as built-ins or within modules. But how do they work? In this practical we will look at a few different sorting algorithms, and visualise how they work.
Gnome sort¶
Gnome sort is a very simple sorting algorithm. Imagine you have a line of objects that need to be sorted. If the object next to you and the one immediately in front of it are in the wrong order, you swap them and take one step backwards (unless you are at the start of the line). Otherwise, you take one step forward. You repeat this, starting from the first object, until all objects are sorted.
Bubble sort¶
Bubble sort is rather similar. You start at the first object, and walk forwards down the line. If the object next to you is in the wrong order compared to the object in front of it, you swap them. However, you do not take any backwards steps. Once you get to the end of the line, you go straight back to the start and repeat until you have all objects in the desired order.
Selection sort¶
In selection sort, you guarantee that all objects behind you are sorted. As you walk forward down the line of objects, you look at the object next to you and everything in front of it. You identify which of these objects is the smallest, and swap it with the object next to you. You then take one step forward and repeat.
Shell sort¶
In Shell sort, you use the bubble sort algorithm, except that you initially only compare every \(N\)-th object. You gradually reduce \(N\) as sorting proceeds. For example, suppose you wish to sort objects labelled
ABCDEFGHIJKLMNO
Initially you sort every 5th object, using bubble sort. So, you ensure that the sequences
A F K , B G L , C H M , D I N and E J O
are each correctly sorted individually (i.e., A, F and K are now in the correct order, but A, B and C may not be). Next, you might sort every 3rd object, looking at the sequences
A D G J M , B E H K N and C F I L O.
Finally, you do a third pass where you sort objects individually, i.e. you apply bubble sort to the entire list.
For more details, and a variety of other sorting algorithms, see this Wikipedia page.
We can make a disordered array of integers:
import numpy as np
data = np.arange(100)
np.random.shuffle(data)
data
array([50, 51, 67, 71, 41, 19, 17, 25, 88, 3, 35, 65, 86, 94, 16, 9, 73,
89, 12, 76, 32, 78, 91, 31, 97, 20, 58, 62, 43, 39, 42, 87, 57, 99,
68, 75, 74, 55, 30, 8, 22, 4, 24, 70, 15, 2, 38, 46, 72, 92, 79,
23, 10, 45, 40, 64, 54, 49, 84, 36, 48, 90, 7, 21, 80, 61, 29, 5,
34, 6, 14, 95, 66, 82, 98, 52, 53, 47, 81, 1, 59, 69, 93, 11, 13,
83, 85, 28, 27, 18, 37, 56, 0, 44, 33, 26, 63, 96, 60, 77])
Write your own implementations of the four sorting algorithms, and make an animation like this showing how the array changes as sorting proceeds.
Gnome sort is a very simple sorting algorithm. Imagine you have a line of objects that need to be sorted. If the object next to you and the one immediately in front of it are in the wrong order, you swap them and take one step backwards (unless you are at the start of the line). Otherwise, you take one step forward. You repeat this, starting from the first object, until all objects are sorted.
def sort_gnome(x):
"""gnome sorting
Parameters
----------
x : 1d array
the array to sort
"""
length = len(x)
i = 0
while i < len(x)-1:
n2 = x[i+1]
n1 = x[i]
if n2 < n1:
x[i+1] = n1
x[i] = n2
i = i-1
if i < 0:
i = 0
else:
i += 1
return x
x2 = sort_gnome(data)
x2
array([ 0, 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, 26, 27, 28, 29, 30, 31, 32, 33,
34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50,
51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67,
68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84,
85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99])
from IPython.display import HTML
fp = open('sortingalgorithms.html','r')
html = fp.read()
fp.close()
HTML(html)