Laboratory 9
Due at the beginning of class, Wednesday, 4/16
In today's lab you will experiment with the running times for different sorting algorithms that we learned in class (and some we will be learning soon).
The code for this lab is available in the directory:
Start the lab as follows:
To run this code, you should compile the file, test_insertion_sort.cc. This file includes not only the list.h file, but also the list.cc file (this is necessary so that the correct object code can be created for the given List_entry type). It also includes key.h and key.cc, sortable_list.h and sortable_list.cc files. Therefore, to compile this code, you can use the command:
Run the test_insertion_sort program to find the number of comparisons made by insertion sort for list lengths of 10, 20 and 100. Write the number of comparisons in the table given in the lab 9 answer sheet.
b) The sortable_list.h and sortable_list.cc files also contain implementations for selection_sort(), merge_sort() and quick_sort(). You should test these the same way you tested insertion_sort(). Here's how to do it with selection_sort().
c) Write the formulas for the average running time of insertion sort and selection sort for the three conditions tested (sorted list, reverse-sorted list, average random list). Use the formulas to compute the expected values for n = 100. Include these in the table.
d) How do the sorting algorithms compare for each of the types of lists tested (sorted in order, sorted in reverse order, random)?
a) Add a bubble_sort() function to the Sortable_list class definition. You will need to add the prototype in the sortable_list.h file and an implementation in the sortable_list.cc file.
Note:
Now create a test_bubble_sort.cc file in the same way as you created the other test files in problem 1. Test the number of comparisons for list lengths of 10, 20 and 100 for bubble_sort, and add the results to the table on the lab9 answer sheet.
b) What is the formula for the number of comparisons performed by bubble sort in each of the conditions tested? How did you arrive at this formula? Include this formula on the table and use it to compute the expected number of comparisons for n = 100 (and include the answers in the table).
c) How does the performance of bubble_sort() compare to the other sorting functions tested in this lab?
What To Turn In.
Be sure that the file prologue for each file contains your name, course, lecture section, date and purpose of the program or a description of the contents of the file (e.g. specification of the stack class).
Reminder.
Be sure to save a copy of each file in your labs directory. It is your responsibility
to keep the copies of all programs written for this course until your
graded assignment is returned.
Home | | Syllabus | | Assignments | | Lecture Notes