Lesson Objective
- Understand how to use the bubble sort algorithm.
- Understand how to use the insertion sort algorithm.
- Understand how to use the merge sort algorithms.
KS3, GCSE, A-Level Computing Resources
Imagine you have a messy list of items.
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 |
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 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.
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!