Sorting

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.

6 4 2 9 0 1 5
             p
4 6 2 9 0 1 5
4 2 6 0 9 1 5
4 2 6 0 1 9 5
4 2 6 0 1 5 9   everything to the right of p is sorted
           p    everything to the right of p is
                greater than or equal to everything to
                the left.

4 2 6 0 1 5 9   
           p    
4 2 6 0 1 5 9   
2 4 6 0 1 5 9   
2 4 0 6 1 5 9   
2 4 0 1 6 5 9   
2 4 0 1 5 6 9   
         p
2 4 0 1 5 6 9   
2 0 4 1 5 6 9   
2 0 1 4 5 6 9   
       p
0 1 2 4 5 6 9   
     p
0 1 2 4 5 6 9   
   p
0 1 2 4 5 6 9
 p


def bubble(x):
    p = len(x)
    while p > 1

list has size n. first pass n - 1 second n - 2 third n - 3 . .. last 1 ---------------------- sum(k, k 1..(n-1)) n(n-1)/2 at worst proportional to n*n. this algorithm is O(n^2).

list has size n. first pass n - 1 second n - 2 third n - 3 . .. last 1 ---------------------- sum(k, k 1..(n-1)) n(n-1)/2 at worst proportional to n*n. this algorithm is O(n^2).

list has size n. first pass n - 1 second n - 2 third n - 3 . .. last 1 ---------------------- sum(k, k 1..(n-1)) n(n-1)/2 at worst proportional to n*n. this algorithm is O(n^2).

list has size n. first pass n - 1 second n - 2 third n - 3 . .. last 1 ---------------------- sum(k, k 1..(n-1)) n(n-1)/2 at worst proportional to n*n. this algorithm is O(n^2).

list has size n. first pass n - 1 second n - 2 third n - 3 . .. last 1 ---------------------- sum(k, k 1..(n-1)) n(n-1)/2 at worst proportional to n*n. this algorithm is O(n^2).

list has size n. first pass n - 1 second n - 2 third n - 3 . .. last 1 ---------------------- sum(k, k 1..(n-1)) n(n-1)/2 at worst proportional to n*n. this algorithm is O(n^2).

list has size n. first pass n - 1 second n - 2 third n - 3 . .. last 1 ---------------------- sum(k, k 1..(n-1)) n(n-1)/2 at worst proportional to n*n. this algorithm is O(n^2).

list has size n. first pass n - 1 second n - 2 third n - 3 . .. last 1 ---------------------- sum(k, k 1..(n-1)) n(n-1)/2 at worst proportional to n*n. this algorithm is O(n^2).

list has size n. first pass n - 1 second n - 2 third n - 3 . .. last 1 ---------------------- sum(k, k 1..(n-1)) n(n-1)/2 at worst proportional to n*n. this algorithm is O(n^2).

Trickle Down!

6 4 2 9 0 1 5
 p

Everything to the left of p is sorted.
On the right: It's a jungle out there!

increment p.
`
6 4 2 9 0 1 5
   p

check neighbor to left.  If neighbor is bigger,
swap.  (trickle down)

4 6 2 9 0 1 5
   p

increment p

4 6 2 9 0 1 5
     p

4 2 6 9 0 1 5
2 4 6 9 0 1 5
     p

increment p.

2 4 6 9 0 1 5
       p
noting to do

2 4 6 9 0 1 5
         p
2 4 6 0 9 1 5
2 4 0 6 9 1 5
2 0 4 6 9 1 5
0 2 4 6 9 1 5
         p
0 2 4 6 9 1 5
           p
0 1 2 4 6 9 5
0 1 2 4 6 9 5
             p
0 1 2 4 6 9 5
0 1 2 4 6 5 9
0 1 2 4 5 6 9
             p

A Sketch of an Algorithm for you!