1

mrahmedcomputing

KS3, GCSE, A-Level Computing Resources

Lesson 5. Sorting Algorithms


Lesson Objective

  1. Understand how to use the bubble sort algorithm.
  2. Understand how to use the insertion sort algorithm.
  3. Understand how to use the merge sort algorithms.

Lesson Notes

Bubble Sort

Imagine you have a messy list of items.

  1. Start at the beginning: Compare each item to the one next to it.
  2. Swap if bigger: If an item is bigger than its neighbor, swap their positions in the list.
  3. Move on, but leave the biggest behind: After comparing everything, the biggest item will be at the end.
  4. Repeat, shrinking the list: Do the same comparisons again, but skip the end (already the biggest). This moves the next biggest item back one step.
  5. Keep going until sorted: Continue comparing and swapping, moving towards the front of the list, until all items are in order from smallest to biggest (or biggest to smallest, depending on the sorting goal).

This process is like bubbles of larger items constantly "floating" to the end as the list gets more ordered.

Result of the first pass

9 5 4 15 3 8 11 2
5 9 4 15 3 8 11 2
5 4 9 15 3 8 11 2
5 4 9 15 3 8 11 2
5 4 9 3 15 8 11 2
5 4 9 3 8 15 11 2
5 4 9 3 8 11 15 2
5 4 9 3 8 11 2 15

Result of the second pass

5 4 9 3 8 11 2 15
4 5 9 3 8 11 2 15
4 5 9 3 8 11 2 15
4 5 3 9 8 11 2 15
4* 5 3 8 9 11 2 15
4 5 3 8 9 11 2 15
4 5 3 8 9 2 11 15
4 5 3 8 9 2 11 15

Insertion Sort

This algorithm sorts one data item at a time. One item is taken from the list, and placed in the correct position. This is repeated until there are no more unsorted items in the list. Example below:

9 5 4 15 3 8 11 2
5 9 4 15 3 8 11 2
4 5 9 15 3 8 11 2
4 5 9 15 3 8 11 2
3 4 5 9 15 8 11 2
3 4 5 8 9 15 11 2
3 4 5 8 9 11 15 2
2 3 4 5 8 9 11 15

Merge Sort

Merge sort solves a sorting problem by dividing the list to be sorted into smaller sub-lists, recursively conquering each sub-list by sorting it, and then combining the conquered sub-lists in a specific way to ensure the overall list is sorted.

1. Split the list into individual items

39 17 24 43 12 8 48 31

2. Merge into pairs

17 39 24 43 8 12 31 48

3. Merge into sublists

17 24 39 43 8 12 31 48

4. Merge into final sorted list

8 12 17 24 31 39 43 48

Note: The split process has not been included in this example.


Sort Comparisons

Choosing the right sorting algorithm depends on your data size and needs. For small lists or partially sorted data, Insertion Sort shines, while Bubble Sort is simple but slow for larger datasets. Merge Sort reigns supreme for large datasets due to its speed, but it requires more memory. Think of them as tools: Insertion Sort for quick fixes, Bubble Sort for simple needs, and Merge Sort for heavy-duty tasks. Remember, the best algorithm depends on your specific situation!


3