Bubble Up! Here is the idea: Go through the unsorted list and visit each pair of neighboring elments from left to right. If a given pair is out of order, swap the elements.
What does this cause to happen?
Going from left to right, check each pair of neighbors. if they are out of order, swap 'em; if not, move on.
2 6 0 9 5 4
p
2 0 6 9 5 4
2 0 6 5 9 4
2 0 6 5 4 9
2 0 6 5 4 9
p
Repeat, but we don't have to deal with any
elements to the right of p.
2 0 6 5 4 9
p
0 2 6 5 4 9
0 2 5 6 4 9
0 2 5 4 6 9
p
0 2 5 4 6 9
p
0 2 4 5 6 9
p
0 2 4 5 6 9
p
0 2 4 5 6 9
p
You are the computer
8 6 4 9 1 0
p
6 8 4 9 1 0
6 4 8 9 1 0
6 4 8 9 1 0
6 4 8 1 9 0
6 4 8 1 0 9
p
6 4 8 1 0 9
4 6 1 8 0 9
4 6 1 0 8 9
p
4 6 1 0 8 9
4 1 6 0 8 9
4 1 0 6 8 9
p
4 1 0 6 8 9
1 0 4 6 8 9
p
1 0 4 6 8 9
0 1 4 6 8 9
p
What do we need to keep track of?
where we are in the swap shop
p - pointer to the end
Input is a list of items that can be sorted.
to start, put p = len(x)
Use a loop to control the swapping of miscreant
out of order neighbors.
Trickle Down!
6 8 5 0 2 4
p
6 8 5 0 2 4
p
6 8 5 0 2 4
p
6 5 8 0 2 4
5 6 8 0 2 4
p
A Sketch of an Algorithm for you!