Paul's Python CoursePPC

Selection sort and insertion sort

Not met yet

Selection sort finds the smallest item left and swaps it into the next place, one pass per place. Insertion sort takes each item in turn and slides it left past every bigger one. Both are O(n²) on a jumbled list. Selection sort always does the same amount of looking, but insertion sort stops sliding as soon as the item to its left is smaller, so on a list that's nearly in order it's close to O(n).

Try it

main.py

Output

Press Run and what your program prints shows up here.

Easy to get wrong

  • Thinks one pass of a simple sort puts more than one item in its final place.
  • Thinks swapping two items in a list shifts the items between them along by one place.
  • Thinks a variable that marks a position, like lightest, holds the item at that position.
  • Thinks selection sort finishes early on a list that is already in order.
  • Thinks a = b followed by b = a swaps two values, when the first line has already overwritten a.

Where it comes up