Algorithm Race

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

What you will learn

A benchmark races programs on the same data, at the same size, with the same counter.
Which sort wins depends on the track: insertion loves nearly sorted data, selection doesn't care, merge sort wins when n is big.
Change one thing at a time, or the race tells you nothing. AI models are compared the same way.

Which sort wins? It depends on the track.
First bet: who wins on an almost sorted track?
Four tracks, two racers, 20 numbers each.
The shorter bar finishes first. Race them.
Change the size and the track.
Try at least three settings.
Benchmarks.
A benchmark is a race between programs: same data, same size, same way of counting.
Run it on several tracks: random, sorted, reversed, nearly sorted. One track can hide a weakness.
Now build your own racers. Each keeps a steps counter.
Racer 1: insertion sort with a step counter.
One step per card, plus one per shift.
Racer 2: selection sort with a step counter.
One step per comparison.
Race your two racers on all four tracks.
Your code runs for real, 20 numbers per track.
Read your results: who won each track?
Tap the winner in every row, then Check.
On reversed data every pair is out of order, so insertion does all 190 shifts plus 19 looks: 209 against selection's 190.
Someone posted this race: insertion crushes selection. What's wrong?
Tap a track chip to change that racer's data until the race is fair.
Challenge: when does merge sort take over?
Merge sort against insertion on random data. Find the smallest n where merge wins from then on. 5 tests.
Insertion sort on a reversed list of 100. How many shifts?
Each shift fixes exactly one pair that is out of order. Reversed, all 100 x 99 / 2 = 4950 pairs are.
My sorting race.
Your table, from your own racers. Tap a track to replay it.

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