Reading

Videos and slides

Selection and insertion sort

Note: The video uses the terminology "quadratic complexity". We will give the definition of "complexity" later in the course, but here is a summary (we'll go through this in the live lecture). If an algorithm's runtime is proportional to the square of the input size (like selection sort), then we say that it has quadratic complexity or takes quadratic time. The complexity tells us how the runtime of an algorithm grows with the size of its input. For example:

Linear search has linear complexity: the runtime is proportional to the input size. If we run it on an input twice as big, it takes twice as long.
Binary search has logarithmic complexity: the runtime is proportional to the logarithm of input size. If we run it on an input twice as big, it takes a constant amount longer (in the case of binary search, it has to do one more array access).
Selection sort has quadratic complexity. If we run it on an input twice as big, it takes four times as long.

Extra resources

VisuAlgo - interactive animations of sorting algorithms (and more)
Sorting out sorting - a "retro" (but good) video about sorting from the 80s
AlgoRythmics - sorting algorithms visualised using Hungarian folk dances