Lab Dates: On-line due to the lost week of hurricane Sandy. This lab is due by midnight Friday December 14, 2012.

Today's lab focuses on sorting and searching (Chapter 13).

Sorting Visualization

The on-line lecture (available on Blackboard) focuses on the searching and sorting. This lab has visualizations of the sorts covered in the lecture. Download the sortGUI.py file to your machine and run it. Remember, that it will need the graphics.py file in the same directory.

The program generates 40 random numbers and first sorts the list with the selectionSort algorithm from the textbook. 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 largest number and then interchanges it with the last number in the list. It then repeats looking for the next largest number and puts that in the second-to-last 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 largest number moving each time?

Next, the program generates 40 random numbers and sorts the list with the mergeSort algorithm from the textbook. mergeSort has a very different strategy:

To sort each half, the function calls itself (mergeSort) to perform the sort. This is an example of recursion, which just means a function that calls itself. For our list of 40 numbers, this means the program will split the list in half, sort the first 20 numbers, then the next 20 numbers, and merge the results back to form a single sorted list. Run the program several times, paying attention to the end of the second sort. You can see the first sorted half and the second sorted half merging to form a single sorted list. If you run the program again, and look earlier, you can see the left half of the left side (first 10 slots) and the right half of the left side (next 10 slots), being merged together to form a sorted list of the first half.

mergeSort is very fast but harder to implement in code. selectionSort is slower to run but easier to implement.

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] )
            done
	 done
      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 )
   

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(a,w):
         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]
               drawBox(a, j, w)
               drawBox(a, j+1,w)
            time.sleep(.1)
   

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?

After completing your program, go to Assignments in Blackboard and click on the link: Lab 11. Use the file upload interface to upload your program. Remember to click the Submit button before closing the lab exercise.