Today's lab focuses on an application of nested loops: sorting lists of numbers.
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:
[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 placeThe 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 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?
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 NThis 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 - 2Since 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]
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.
# 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()
If you finish early, you may work on the programming problems.