Thu Dec 4

Hope you're all busy working on your projects! I look forward to seeing what you have on our last class on Tuesday.

sorting

We'll discuss some of the basic ideas of one of the classic CS algorithms: how to put a list of numbers into order.

Turns out there are many ways ... some faster than others, and some only for particular situations.

Trade-offs are typically: time it takes (as the number of elements n gets bigger), extra memory, complexity, can it be run in parallel,

Here are a few well known ones :

• selection sort : n*n time; first one many folks invent
• merge sort : n*log(n) time; divide-and-conquer
• radix sort : n time; just put each into the right bin

And here are some visualizations :

• select sort as a gypsy dance
• merge sort as a german folk dance
• sorting animations

practice ...

• https://adventofcode.com/