TwiddleLab / Code / Algorithms in Motion

Selection Sort

Lesson 3 of 11 · 7 min · Free, no account needed

What you will learn

• Selection sort: find the smallest of the unsorted part, swap it to the front, repeat.
• The sorted prefix grows by one each pass, like a wall moving right.
• On n items it makes (n - 1) + (n - 2) + ... + 1 = n(n - 1)/2 comparisons: 28 for 8, 4950 for 100.
• It makes that many even when the list is already sorted.

Start the lesson

How the lesson goes

1. Sort your playlist by length: find the shortest, put it first, repeat.

   Finding the shortest means comparing songs. How many comparisons to sort all 8?

2. Sort it yourself. Tap the shortest song right of the wall.

   The counter adds every comparison the sort needs to be sure.

3. Now watch the machine do it, one comparison at a time.

   Step, Pass or Run. Watch the staircase on the right.

4. Selection sort.

   Selection sort: find the smallest item in the unsorted part, swap it to the front of that part, repeat.

   The left part is the sorted prefix. It grows by one item every pass and never changes again.

   On n items: (n - 1) + (n - 2) + ... + 1 comparisons. For 8 items that's 28.

5. Write selection sort, with a comparison counter.

   best is the index of the smallest so far. Swap through t, a spare box.

6. Show the list after 3 passes of selection sort.

   Drag a bar onto another to swap them, then Check.

   Each pass swaps just two bars: the smallest of the unsorted part and the bar at the front of it. So after 3 passes, only the first 3 places are settled.

7. 100 songs. How many comparisons?

   99 + 98 + ... + 1. The square of pairs gives a shortcut.

   The comparisons are every pair of different songs, counted once: n x n cells, minus the n on the diagonal, halved. 100 x 99 / 2 = 4950.

8. Sort sprint.

   Three lists, growing. Tap the smallest each time. Fast, and no misses.

9. Your selection sort meets a list that's already sorted.

   Which needs fewer comparisons? Tap a list, or They take the same, then Check.

   The inner loop runs for j from i + 1 to the end no matter what the values are. The count depends only on n, not on the order.

Previous lesson: Linear vs Binary Search, Revisited · Next lesson: Insertion Sort · Part of the course: Algorithms in Motion

Lessons are interactive and need JavaScript. Turn it on to play them.