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:

• find the smallest number in the list and move to the front,
• repeat the first step on the last part of the list (i.e. lst[1:0])
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:
• the inner loop and decision statement find the smallest number (not already in place), and
• the outer loop repeatedly goes through the remaining list until there are no more to put in order.

### 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 not 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:

• ```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
```
• ```func bubblesort( var a as array )
```
This first lines says we have a function with an array variable called a. In python, we define functions with the def keyword:
```	def bubbleSort(a):
```
• ```    for i from 2 to N
```
This next line is a for loop, but what is N? Usually, N or n refers to the length of the list, so, let's set that up as a variable first, then write out the for loop:
```	N = len(a)
for i in range(2, N+1):
```
Note that their for loop goes from 0 upto and including N, so, we need to change the range accordingly.
• ```        for j from 0 to N - 2
```
Since we have N defined, we can easily write out this for-loop:
```
for j in range(N-1):
```
• ```           if a[j] > a[j + 1]
```
We need one small addition to make this line proper python:
```		   if a[j] > a[j+1]:
```
• ```              swap( a[j], a[j + 1] )
```
Lastly, we need to swap the two values. In python, we can do this in one line with simultaneous assignment:
```			  a[j],a[j+1] = a[j+1],a[j]
```
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~

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()
```

If you finish early, you may work on the programming problems.