Selection sort: find the smallest
Watch selection sort put a list in order by finding the smallest number left and swapping it to the front, pass after pass. Count its comparisons and swaps, and compare it with bubble sort on a jumbled, a sorted and a reversed list.
Core concept
Selection sort looks through the unsorted part for the smallest number and swaps it into the next place at the front; it always makes the same number of comparisons, but at most one swap per pass
Topic: Algorithms
Selection sort is another way to put things in order. Imagine picking the shortest student from a group and sending them to the front of the line, then picking the shortest of those left for the second place, and so on. The computer does the same with numbers. In each pass it looks through the part of the list that is not sorted yet, remembers where the smallest number is, and at the end of the pass swaps that number into its place at the front. The sorted part at the front grows by one each pass. Selection sort always compares every pair it needs to, so its comparisons never change, but it makes at most one swap in each pass, which is far fewer than bubble sort when the list is badly out of order.
What you will learn
- Describe one pass of selection sort: find the smallest, then swap it to the front.
- Trace the smallest-so-far (min) through a pass.
- Count the comparisons and swaps selection sort makes.
- Compare the swaps of selection sort and bubble sort on the same list.
Before you start
- Know how bubble sort compares neighbours and swaps them.
Materials
- A notebook to write the counts
Equipment
- None
Procedure
- Run selection sort on the jumbled list and read the comparisons, swaps and passes.
- Step through one pass and watch the smallest-so-far change.
- Sort the reversed list with selection sort, then with bubble sort, and compare the swaps.
- Answer the practice challenges.