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.

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.

from sys import argv
from random import shuffle
def swap(x, k, l):
    x[k], x[l] = x[l], x[k]

def bubble(x):
    p = len(x)
    while p > 1:
        for k in range(p - 1):  #this does a single neighbor-check pass
            if x[k] > x[k+1]:
                swap(x, k, k+1)
                #print(f"swapping: {x}")
        p -= 1
        #print(f"Pass {p}:  {x}")

n = int(argv[1])
x = list(range(n))
shuffle(x)
print(x)
bubble(x)
print(x)

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!