Bubble sort, swap by swap
Watch bubble sort put a list of numbers in order, one comparison at a time. Count the comparisons and swaps, see the largest number bubble to the end after every pass, and compare a jumbled, a sorted and a reversed list.
Core concept
Bubble sort compares each pair of neighbours and swaps them when they are in the wrong order; each pass carries the largest number left to the end, and a pass with no swaps means the list is sorted
Topic: Algorithms
Sorting means putting things in order, like arranging students by height for a photo. Bubble sort is one of the simplest ways a computer can do it. It looks at the first two numbers: if the left one is bigger, it swaps them. Then it moves one place along and compares the next pair, all the way to the end of the list. One trip along the list is called a pass. After the first pass the largest number has “bubbled up” to the end, like a bubble rising in water. Each new pass places the next largest number, so the sorted part at the end grows. If a whole pass makes no swaps, everything is already in order and the sort can stop early.
What you will learn
- Describe one pass of bubble sort: compare neighbours and swap when out of order.
- Explain why the largest number reaches the end after the first pass.
- Count the comparisons and swaps bubble sort makes on a list.
- Compare how much work bubble sort does on sorted, jumbled and reversed lists.
Before you start
- Know how to compare two numbers with > and <.
Materials
- A notebook to write the counts
Equipment
- None
Procedure
- Run bubble sort on the jumbled list and read the comparisons, swaps and passes.
- Step through one pass and watch which pairs are compared and swapped.
- Run it on the sorted list and on the reversed list, and compare the counts.
- Answer the practice challenges.