What to hand in

algo with a sort command, passing go test ./..., plus a measurement report.

1. The quadratic curve

Measure all three algorithms at n = 1,000 / 10,000 / 50,000, -order shuffled:

n	algorithm	comparisons	swaps	wall

Show that the comparison count grows ×100 when n grows ×10. Does your time grow the same way? If not, explain it using step 5.

(You do not have to run bubble sort at a hundred thousand — it took a minute and a half in the lesson. If you do, record the time.)

2. Four orders

One algorithm — insertion — four orders, n = 10,000:

order	comparisons	swaps	wall
sorted
nearly
shuffled
reverse

Give the ratio between the best and worst case.

3. Swaps versus comparisons

Selection sort makes more comparisons than bubble and is still faster.

Measure both and work out how many times more expensive one swap is than one comparison on your machine. Give the number and how you got it.

4. When the sort pays for itself

In lesson 6's homework you worked out how many binary searches repay one sort.Slice.

Do it again with your own sort. How many searches repay one InsertionSort of 100,000 items? Does the answer even make sense?

5. The decision

One paragraph: in your library, items are added one at a time and occasionally you need a sorted list.

What will you do? Sort every time? Keep it permanently sorted? Sort only before a search? Justify with the numbers from parts 1 and 2, and say which of the three algorithms fits here — if any of them does.