As usual, create a directory to hold today's activities:
$ mkdir ~/cs170/labs/lab14 $ cd ~/cs170/labs/lab14
We now know two different ways for sorting lists of integers. When would we use one of these algorithms versus the other? Why do more than one algorithm for this? Is one just much better than all of the others?
And what does it mean to compare these algorithms? What do we compare? How do we compare them? Today we will talk about these comparisons, so we can get a good grasp on how these comparisons will look in the future.
Bubble sort is another sorting algorithm that we can use. It's one of the easier algorithms to implement, and is quite intuitive as far as how it actually achieves a sorted list at the end. We discussed in class that it seems maybe less efficient than the other algorithms we have seen. Let's find out!
Copy your sorting.py file from last lab to this labs directory:
$ cp ../lab13/sorting.py .
Create a function
called bubble_sort(a_list), which takes a list of
integers, and returns a copy of a_list in sorted order. You should
implement the bubble sort algorithm discussed in the textbook.
Make sure you test your function on several lists of various sizes, just to make sure that it works correctly.
my_list = [5, 4, 3, 2, 1] my_sorted_list = bubble_sort(my_list) print(my_list) #Prints [5, 4, 3, 2, 1] print(my_sorted_list) #Prints [1, 2, 3, 4, 5] my_list = [4, 2, 1, 3, 5] my_sorted_list = bubble_sort(my_list) print(my_list) #Prints [4, 2, 1, 3, 5] print(my_sorted_list) #Prints [1, 2, 3, 4, 5]
You will need two for loops for bubble sort. One will determine the number of times you perform the bubble operation. The second loop will be where the bubbling occurs.
Your internal for loop should just compare two successive elements in the list, if they are out of order just swap them.
Your swap method above probably utilized a temporary variable to perform a swap. However, there is a clever use of python syntax that you can use in order to accomplish the swap in one line. Figure that out, and these bonus points are yours.
We have the that says binary search should be quicker than linear search, at least in the worst case when the list sizes are arbitrarily large. But it would be nice to have validation for that. I showed you in lecture today how we can actually time our algorithms to accomplish that goal. Let's use some of Python's built in mechanisms to time our sorting algorithms to see if we can justify our assumptions on how well these algorithms work.
Create a file called timed_sorting.py, which will time your actual execution times for all three of your sorting algorithms
Python provides a built in library for timing your code, called
timeit.
This module includes a class called Timer, which can be
used to create an object for timing a given function. You can use
the code from the lecture, but you will have to make a few key
changes to make sure the timings are fair.
You will want to create a list of integers to time your sorts on.
To create a sorted list of integers, you can use
the range function.
>>> my_list = list(range(10)) >>> print(my_list) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
For fairness, create a class called Timing, which will
have an attribute for the list being searched. You should have
methods
called test_selection, test_insertion,
and test_bubble. This should simply call your sorting
algorithms on the list stored in the attribute.
Once you have your class created, You then just need to create a timer object that will call your testing methods. Your method should return a tuple of floating point values, the times for both selection, insertion, and bubble sorts respectively.
Time your three sorting functions on list sizes from 100 to 1000,
incrementing by 50 each time. For
the sake of consistency, you will want the timer to execute at least
1000 times per trial. You can specify this when you call the
timeit method of the Timer object.
>>> timing_object = Timing(list(range(100)))
>>> selection_time, insertion_time, bubble_time = timing_object.time_sort()
>>> print("Selection:", selection_time, "Insertion:", insertion_time, "Bubble:", bubble_time)
Selection: #.#### Insertion: #.#### Bubble: #.####
It's great that we can time these algorithms, but it's hard to read the output of these programs. What would be better is if we could visually see how they compare.
Write a program that takes three lists (which represents timings of algorithms). This program should use Tkinter to plot the results. You will need to scale your results so they fill as much of the window as possible.
When you have finished, create a tar file of your lab14
directory. To create a tar file, execute the following commands:
cd ~/cs170/labs tar czvf lab14.tgz lab14/
To submit your activity, go to inquire.roanoke.edu. You should
see an available assignment called Lab Assignment 14.
Make sure you include a header listing the authors of the file.