Selection Sort

Selection sort finds the smallest value in the list and then swaps it with the value at position 0. It then looks from position 1 onwards for the second smallest value (the smallest is at position 0) and swaps that one with the one at position 1, does this for all remaining positions in the list.

• Learn the basics of big-O notation
• Determine why selection sort uses O(n²) or quadratic time in any case
• Determine why selection sort uses O(1) or constant extra memory in any case, i.e. it works in-place.
• Determine why selection sort is stable. This means that if * and # are equal values in the list, and originally * is left of #, then * will remain left of # after the list is sorted.
• Briefly discuss applications.

• Hear the 17-line, 90 second selection sort song:
  1. The first part covers big-O analysis facts.
  2. The second covers the pseudocode which will help you program selection sort in any programming language.
• Watch me demonstrate how to use the song lyrics to implement the algorithm in Python, the most straightforward programming language (in my opinion).