selection sort:
- loop [0], [1], etc., correcting each slot as you go
- to correct [i], find smallest value in [i+1] on, and swap them
- i.e., find smallest item in remaining area, swap with current item

insertion sort:
- find first no. out of sequence in remaining part
- insert into correct place in sorted part, which grows

bubble sort:
- in each pass, compare [0] and [1], [1] and [2], etc.
- swap elements when out of order
- at end of each pass, largest remaining element has bubbled to end

in all sorts:
- sorted part grows, unsorted shrinks until size=0
- all are O(n**2)

--

Practice problems:

1) Sort the following list by bubble sort. Show the array at the end
   of each pass (i.e. each time through the outer loop).

26 45 17 65 33 55 12 18


2) Same for insertion sort.

28 18 21 10 25 30 12 71 32 58 15


3) Same for selection sort.

36 55 17 35 63 85 12 48 3 66


--

Answers:


1) Bubble sort

26 45 17 65 33 55 12 18
26 17 45 33 55 12 18 65
17 26 33 45 12 18 55 65
17 26 33 12 18 45 55 65
17 26 12 18 33 45 55 65
17 12 18 26 33 45 55 65
12 17 18 26 33 45 55 65


2) Insertion sort

28 18 21 10 25 30 12 71 32 58 15
18 28 21 10 25 30 12 71 32 58 15
18 21 28 10 25 30 12 71 32 58 15
10 18 21 28 25 30 12 71 32 58 15
10 18 21 25 28 30 12 71 32 58 15
10 12 18 21 25 28 30 71 32 58 15
10 12 18 21 25 28 30 32 71 58 15
10 12 18 21 25 28 30 32 58 71 15
10 12 15 18 21 25 28 30 32 58 71


3) Selection sort

36 55 17 35 63 85 12 48  3 66
 3 55 17 35 63 85 12 48 36 66
 3 12 17 35 63 85 55 48 36 66
 3 12 17 35 36 85 55 48 63 66
 3 12 17 35 36 48 55 85 63 66
 3 12 17 35 36 48 55 63 85 66
 3 12 17 35 36 48 55 63 66 85

Note: Duplicate lines omitted, i.e. lines were not recopied if nothing
changed. If you write a program to generate these, duplicate lines wil
be included. You can do it either way.