CSCI 132 Data Structures--Spring 2014

    Home | | Syllabus | | Assignments | | Lecture Notes

    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:

      ~csci132/labs/lab9

    Start the lab as follows:

    • Copy the code for lab9 into your labs folder by typing:
        cp -r ~csci132/labs/lab9 labs/.
    • Verify that the lab9 directory contains the following files:
      • list.h
      • list.cc
      • key.h
      • key.cc
      • sortable_list.h
      • sortable_list.cc
      • test_insertion_sort.cc

    1. Comparing different sorting algorithms

    a) The test_insertion_sort.cc file has all the code necessary to prompt the user and enter a list length. It then counts the number of comparisons made by insertion_sort() for a list of the given length for the following cases:

    1. A list that starts out already sorted
    2. A list that starts out in reverse sorted order
    3. The average for 100 different random lists.

    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:

      g++ -g -Wall test_insertion_sort.cc -o test_insertion_sort

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

    1. Save the test_insertion_sort.cc file as test_selection_sort.cc
    2. In the new file, change all instances of "insertion" to "selection"
    3. Compile your new program and run it as before.
    4. Write the results for list lengths of 10, 20 and 100 in your table.
    5. Repeat the above 4 steps for merge and quick sorts.

    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)?

    2. Implementing a sorting algorithm

    A well-known algorithm called bubble sort proceeds by scanning the list from left to right, and whenever a pair of adjacent keys is found to be out of order, then those entries are swapped. In this first pass, the largest key in the list bubble sort will have "bubbled" to the end, but the earlier keys may still be out of order. Thus the bubble_sort runs a loop to sequentially move the largest items to the end of the non-sorted portion of the list (similar to selection sort). The first pass through this loop swaps out of order pairs from the beginning to the end of the entire list. Each subsequent iteration of the loop stops swapping one position sooner than the previous iteration, until there is only one "unsorted" item left.

    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:

    • This is not the efficient version of Bubble sort that you implemented in CSCI 131. It does not check to see if the sorting is finished.
    • There is already a swap function defined in the sortable_list class that you can make use of in your implementation of bubble_sort.

    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.

    • A printout of your bubble_sort() function. You do not need to submit the entire sortable_list.cc file, simply copy and paste the bubble_sort() into a separate emacs window and print it. However, make sure the printout includes the usual file prologue information (your name, the date, the assignment, etc.)
    • A printout of the lab9 answer sheet with the results for all the different sorting algorithms tested and the written answers to the questions in parts 1 and 2
    • Submit your lab with the submit function:
        ~csci132/bin/submit csci132 lab9

    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