The slow sorts - top of Musings page

Note # 7
by Nick Duchon

Selection Sort

Step index
  0 1 2 3 4 5 6 7 8 9
0 43
→
 7 10 23 18 4
←		 19 5 66 14
1 4 7
→		 10 23 18 43 19 5
←		 66 14
2 4 5 10
→		 23 18 43 19 7
←		 66 14
3 4 5 7 23
→		 18 43 49 10
←		 66 14
4 4 5 7 10 18
→		 43 19 23 66 14
←
5 4 5 7 10 14 43
→		 19 23 66 18
←
6 4 5 7 10 14 18 19
 23 66 43
7 4 5 7 10 14 18 19 23 66 43
8 4 5 7 10 14 18 19 23 66
→		 43
←
9 4 5 7 10 14 18 19 23 43 66

The blue and orange cells are exchanged on each iteration.
The yellow cells are the part of the list that is currently sorted in each step.

Bubble Sort

Step index
  0 1 2 3 4 5 6 7 8 9
0 43
→
 7
→
 10
→
 23
→
 18
→
 4
→
 19
→
 5
↓
 66
→
 14
↓
1 7 10 23
→		 18
→		 4
→		 19
→		 5
↓		 43
→		 14
↓		 66
2 7 10 18
→		 4
↓		 19
→		 5
↓		 23
→
 14
↓		 43 66
3 7 10
→		 4
↓		 18
→		 5
↓		 19
→		 14
↓		 23 43 66
4 7
→		 4
↓		 10
→		 5
↓		 18
→		 14
↓		 19 23 43 66
5 4 7
→		 5
↓		 10 14 18 19 23 43 66
6 4 5 7 10 14 18 19 23 43 66

Blue cells are elements that are moved rightward (bubbled up) during each sorting pass.
The orange cell is where each blue cell is dropped.

Insertion Sort

Step index
  0 1 2 3 4 5 6 7 8 9
0 43
↓		 7
←		 10 23 18 4 19 5 66 14
1 7 43
↓		 10
←		 23 18 4 19 5 66 14
2 7 10 43
↓		 23
←		 18 4 19 5 66 14
3 7 10 23
↓		 43
←		 18
←		 4 19 5 66 14
4 7
↓		 10
←		 18
←		 23
←		 43
←		 4
←		 19 5 66 14
5 4 7 10 18 23
↓		 43
←		 19
←		 5 66 14
6 4 7
↓		 10
←		 18
←		 19
←		 23
←		 43
←		 5
←		 66 14
7 4 5 7 10 18 19 23 43 66
↓		 14
8 4 5 7 10 18
↓		 19
←		 23
←		 43
←		 66
←		 14
←
9 4 5 7 10 14 18 19 23 43 66

The blue cells are ones added to the list and inserted into the right position in the next line.
The organge cells are where the previous addition was inserted into the list.
The yellow cells are the "in-order so far" part of the list.