Python For GCSE
Sorting Algorithms
For our GCSE, we need to know about three sorting algorithms. These are,
- Bubble Sort
- Insertion Sort
- Merge Sort
Here is some code to use to quickly generate a list of random values to sort.
from random import random lst = [round(random(),3) for i in range(10)]
Bubble Sort
It works as follows,
- Compare the first item in the list with the second.
- If they are in the wrong order, swap them around.
- Compare the second item to the third item.
- If they are in the wrong order, swap them around.
- Continue doing this until the end of the array.
- If you have had to swap any items, repeat the process until no swaps are made.
Take the following array of numbers,
2, 23, 9, 79, 31, 81, 53, 13, 33, 43
On the first pass, some items are swapped, leaving the list as follows,
2, 9, 23, 31, 79, 53, 13, 33, 43, 81
The process is repeated and further swaps are made,
2, 9, 23, 31, 53, 13, 33, 43, 79, 81
Third pass,
2, 9, 23, 31, 13, 33, 43, 53, 79, 81
Fourth pass,
2, 9, 23, 13, 31, 33, 43, 53, 79, 81
Fifth pass,
2, 9, 13, 23, 31, 33, 43, 53, 79, 81
We made some swaps on the last pass, so we still repeat the process. No swaps are made on the sixth pass, so the list is in order,
2, 9, 13, 23, 31, 33, 43, 53, 79, 81
swaps = True
WHILE swaps
swaps = False
FOR p = 0 TO length of lst - 2
IF lst[p] > lst{p+1] THEN
tmp = lst[p]
lst[p] = lst[p+1]
lst[p+1] = tmp
swaps = True
END IF
NEXT P
END WHILE
Insertion Sort
The insertion sort is the closest sort algorithm to the way that we might sort the array if we wrote the numbers on some cards. Imagine that this is the case. You would take the first card and place it on the table. You would then take the second card and place it to the left or right of the first one depending on whether it was greater or less than that item. When the third card is taken, if it goes at the start of the list, you would need to shuffle the other cards to the right to put it in the correct position.
The algorithm for an in-place insertion sort is as follows,
FOR outer = 1 TO LENGTH OF LIST - 1
tmp = lst[outer]
inner = outer
WHILE inner>0 AND lst[inner-1]>=tmp
lst[inner] = lst[inner-1]
inner = inner - 1
lst[inner] = tmp
NEXT outer
Merge Sort
The merge sort is a much quicker algorithm than the other two. It is an example of a divide and conquer algorithm. It works by repeatedly dividing the list in half until the items are in lists of 1. These lists are then merged together into sorted lists until the whole list is sorted.
Here is a Python implementation of the Top-down implementation using lists that is described in pseudocode on the Wikipedia page about the algorithm.
from random import random lst = [round(random(),3) for i in range(20)] def merge_sort(m): if len(m) <= 1: return m midpoint = len(m) // 2 left = m[midpoint:] right = m[:midpoint] left = merge_sort(left) right = merge_sort(right) return merge(left, right) def merge(left, right): result = [] while len(left)>0 and len(right)>0: if left[0]<=right[0]: result.append(left[0]) left = left[1:] else: result.append(right[0]) right = right[1:] while len(left)>0: result.append(left[0]) left = left[1:] while len(right)>0: result.append(right[0]) right = right[1:] return result
Having A Go At Other Sorts
The following are the names of sorting algorithms that you might implement using pseudocode from Wikipedia pages.
- Selection Sort
- Shell Sort
- Quicksort
- Comb Sort
- Cocktail Shaker Sort
- Gnome Sort
Stupid Sort
The Bogosort or Stupid Sort is an interesting one to try with a list of around 10. The way to do this is to shuffle the list, see if it is now sorted. If not, shuffle and check again. Repeat until the list is sorted.
Whilst this is not going to be too efficient, there are a couple of nice challenges for you. The first is to work out how to determine if the list is sorted. The second is to write your program so that it keeps shuffling and checking until the list is sorted. You can then work out the average number of runs required before the sorted list is reached for a given list size.