Today's lab focuses on an application of nested loops: sorting lists of numbers.

Nesting Loops and Conditionals

In Chapters 7 and 8, we discussed loops and decisions (also called conditionals) in detail. Many applications can be programmed by simply combining these two concepts. In today's lab, we will look at two different ways to sort lists of numbers (described in more detail in Chapter 13 of the textbook).

The basic idea of a sorting algorithm is to take a list of items (we'll focus on whole numbers, but you can sort just about anything that you can measure) and return the list in order. So, for example, if you were given as input the list:

[3, 8, 23, 2, 4, 9, 45, 1]
the result of sorting the numbers (in increasing order) would be:
[1, 2, 3, 4, 8, 9, 23, 45]

There are many different approaches to sorting. Here's the idea for the selectionSort algorithm:

So, continuing our example, we would have:
[3, 8, 23, 2, 4, 9, 45, 1]   <-- starting list
[1, 3, 8, 23, 2, 4, 9, 45]   <-- selected 1 and moved it to the front
[1, 2, 3, 8, 23, 4, 9, 45]   <-- selected 2 from remaining lst[1:] and moved it
[1, 2, 3, 8, 23, 4, 9, 45]   <-- selected 3 from lst[2:] but already in place
[1, 2, 3, 4, 8, 23, 9, 45]   <-- selected 4 from lst[3:] and moved it
[1, 2, 3, 4, 8, 23, 9, 45]   <-- selected 8 from lst[4:] but already in place
[1, 2, 3, 4, 8, 9, 23, 45]   <-- selected 9 from lst[5:] and moved it
[1, 2, 3, 4, 8, 9, 23, 45]   <-- selected 23 from lst[6:] but already in place
The python code (from the book's Chapter 13) is:
def selSort(lst):
    n = len(lst)
    for bottom in range(n-1):
        mp = bottom
        for i in range(bottom+1,n):
            if lst[i] < lst[mp]:
                mp = i
        lst[bottom], lst[mp] = lst[mp], lst[bottom]
Note the nested loops:

Sorting Visualization

To make it easier to see the sorting, we have a visualization in sortGUI2.py file to your machine and run it (if it doesn't load, the complete version is available at the bottom of this file). Since it uses Zelle's graphics, it will need the graphics.py file in the same directory.

The program generates 10 random numbers (and pauses, waiting for a mouse click) and first sorts the list with the selectionSort algorithm from above. The code has been modified slightly from the book to update the graphics display as it runs. When the program runs, it repeatedly traverses the list. On its first traversal of the list, it finds the smallest number and then interchanges it with the first number in the list. It then repeats looking for the next smallest number and puts that in the second position in the list. It keeps going putting the next largest number in its place until the whole list is sorted. Run the program several times, paying attention to the first sort only. Can you see the smallest number moving each time?

BubbleSort

Today, we are going to implement another sort, called bubbleSort. While bubbleSort is the most efficient way to sort big lists ( President Obama on the subject, comments), it is easy to understand.

Algorithms are often written in pseudo-code, which is an informal, high-level description:

func bubblesort( var a as array )
    for i from 2 to N
        for j from 0 to N - 2
           if a[j] > a[j + 1]
              swap( a[j], a[j + 1] )
end func
(from www.algorithmist.com/index.php/Bubble_sort)

Let's translate this line-by-line into python:

Putting this altogether, we have:
	def bubbleSort(a):
		N = len(a)
		for i in range(2,N+1):
			for j in range(N-1):
				if a[j] > a[j+1]:
					a[j],a[j+1] = a[j+1],a[j]
To make this function show the graphics, we will add two calls to the drawBox() as well as to sleep() (to slow it down enough to see):
def bubbleSort(lst,w):
    #n = len(lst)
    for j in range(n-1):
        for i in range(n-1):
            if lst[i] > lst[i+1]:
                # draw the bars that are to be swapped            
                drawMovingBars(lst, i, i+1, w)
                # swap the bars
                lst[i], lst[i+1] = lst[i+1], lst[i]
                # draw the bars after they are swapped
                drawMovingBars(lst, i, i+1, w)
   
Note that we need to add w, the graphics window variable, to the formal parameters of our function so that we can use it when calling our drawing function.

Add the bubbleSort() above to your program and try running it. Can you see the largest value "bubble" up to the top? Try running the program multiple times to see the effect.

Sorting Program

# Spring 2014, CMP230, Lab 11
# This is a modified version of sortGUI.py which is available
# on http://comet.lehman.cuny.edu/sfakhouri/teaching/cmp/cmp230/f12/sortGUI.py~
# Modifications are made by Maryam Ghaffari Saadat

from graphics import *
from random import *

n = 10

def main():
    #holds list of numbers to be sorted:
    a = [0]*n 

    #our display window:
    w = GraphWin("Sorting Demo",500,500)
    w.setCoords(-5,0,n*10,n*10)

    #First, display the selection sort (code from book):
    initializeList(a)
    displayList(a,w)
    selSort(a,w)

    #Next, display the bubble sort
    clearScreen(w)
    initializeList(a)
    displayList(a,w)
    bubbleSort(a,w)

    w.getMouse()
    w.close()


#Selection sort function from the textbook, with the addition
#   of code to draw the change each time
def selSort(lst,w):
    n = len(lst)
    for bottom in range(n-1):
        mp = bottom
        for i in range(bottom+1,n):
            if lst[i] < lst[mp]:
                mp = i
        if mp != bottom:
            # draw the bars that are to be swapped
            drawMovingBars(lst, bottom, mp, w)
            # swap the bars
            lst[bottom], lst[mp] = lst[mp], lst[bottom]
            # draw the bars after they are swapped
            drawMovingBars(lst, bottom, mp, w)

#Bubble sort from pseudocode:
def bubbleSort(lst,w):
    #n = len(lst)
    for j in range(n-1):
        for i in range(n-1):
            if lst[i] > lst[i+1]:
                # draw the bars that are to be swapped            
                drawMovingBars(lst, i, i+1, w)
                # swap the bars
                lst[i], lst[i+1] = lst[i+1], lst[i]
                # draw the bars after they are swapped
                drawMovingBars(lst, i, i+1, w)
    

#Set up the initial list to have 40 random numbers:
def initializeList(a):
    for i in range(n):
        a[i] = (n-1)*10*random()+10

def drawMovingBars(lst, box_1_index, box_2_index, w):
    # draw the boxes that are moving, with red outlines 
    drawBox(lst, box_1_index, w, True)
    drawBox(lst, box_2_index, w, True)

    # get a mouse click
    w.getMouse()

    ## uncomment to: wait for .2 seconds (= 2 deciseconds)
    #time.sleep(.2)

    # redraw the boxes without red outlines 
    drawBox(lst, box_1_index, w, False)
    drawBox(lst, box_2_index, w, False)    


#Draw a single box to the screen:
def drawBox(a,i,w, isMoving):
    # clear the space for bar i
    barSpace = Rectangle(Point(i*10, 0), Point((i+1)*10, n*10))
    barSpace.setFill("white")
    barSpace.setOutline("white")
    barSpace.draw(w)

    # create a new bar with hight of a[i] 
    bar = Rectangle(Point(i*10, 0), Point((i+1)*10, a[i]))
    # set the colour of the bar to be a shade of blue
    # the taller the bar, the lighter the blue.
    bar.setFill(color_rgb(0,0,a[i]*(255/(n*10))))
    
    # set the thickness of the outline of the bar to 3 pixels
    bar.setWidth(3)

    # if the bar is moving, set the outline colour to red 
    if isMoving:
        bar.setOutline('red')
    # otherwise set the outline colour to white
    else:
        bar.setOutline("white")

    # draw the bar
    bar.draw(w)


#draw the portion of the list from start to stop:
def displayList(a,w): 
    for i in range(len(a)):        
        drawBox(a,i,w,False)
    
#White out the window, so, we can start again:
def clearScreen(w):
    r = Rectangle(Point(0,0),Point(n*10,n*10))
    r.setFill("white")
    r.draw(w)    

main()