UCR CS 14: Introduction to Data Structures and Algorithms

Spring Quarter 2003 / Class webpage

Lab 06

Remember:

All programming assignments will be done under the Linux operating system, using standard programming tools for that environment.
All programming assignments will be evaluated with the -Wall -Werror compilation options. If your program does not compile with these flags, it will not be evaluated.
Concentrate some effort on style and documentation. A significant portion of your grade will be based on these aspects of your submission.
You have to turnin your codes before you leave.
Every part of your assignment (every file) must begin with our report template header:


// Course:            CS 14

// Lecture Section:   Enter your lecture section number here (1, 2, etc)
// Lab Section:       Enter your lab section number here (21, 22, etc)
// Assignment #:      Enter the assignment number here (1, 2, etc)

// First Name:        Enter your FIRST name here (eg, John)
// Last Name:         Enter your LAST name here (eg, Doe)
// ID Number:         Enter your ID number here (eg, 12-345-678)
// Email address:     Enter your UCR email address here (eg, jdoe@cs.ucr.edu)

// ===============================================================

In this lab, we will work with sorting algorithms performance. First, download the files: array.h, simplearray.h, sorting.h, and testSorting.cc.

File testSorting.cc contains:

Function fill_random that receives an array and populates it with random values.

Function runSorting that receives an array size, an integer, and an algorithm flag. This function creates an array with the given size, and run the algorithm indicated by the flag the given number of times.

Function main calls function runSorting with different input sizes for all sorting algorithms presented in sorting.h

File sorting.h contains two versions of the algorithm bubblesort, and one of selection. At the end of this file, you have just the header for the algorithm insertion.

These files use an ADT array defined in array.h and implemented in simplearray.h.

Turn-in

4 points possible

Your task is to implement a simple and efficient version of the sorting algorithm insertion. Thus, you have to edit the file sorting.h and add your code in body of function insertion. Note: you have to test if your insertion algorithm is really working. You can write a simple function (in another file) that reads an array and prints it in ascending order.

You can not change the files array, simplearray, and testSorting.cc.

Remember to turnin everything at the end of the lab.

4 points possible

Once you have all 4 algorithms, you have to evaluate their performances according to the test cases presented in testSorting.cc.

Your tasks are: run testSorting.cc, and plot the results in one graph.

Figure 1 shows an output of this program.


Algorithm  Array size  Average time
    1           100         0.000
    1           200         4.000
    1           500        22.000
    1          1000        88.000
    1          2000       362.600
    1          4000      1432.000
    2           100         2.000
    2           200         2.000
    2           500        24.000
    2          1000        92.200
    2          2000       348.600
    2          4000      1392.000
    3           100         2.000
    3           200         2.000
    3           500        12.000
    3          1000        54.000
    3          2000       212.400
    3          4000       829.200
    4           100         0.000
    4           200         2.000
    4           500        10.000
    4          1000        42.000
    4          2000       156.200
    4          4000       623.000

Figure 1. testSorting output: first column identifies the algorithm, second column presents the input size, third column shows the average time.

Graph format. Draw a line chart with input size on the x axis, and running time on the y axis. As figure 2.

Figure 2. Example of a graph

Bonus, more 3 points

About bonus credit. This part of your work may give you a chance to increase your grade. If you already have an A, this may help you to add a beautiful A+ in your records. Note that you only get the bonus point if you complete the turn-in part.

1. In a file called performance, include the performance data you collected (each in the form of a table), compare the actual performance of these algorithms to their asymptotic complexity, and explain your "theories" (if you have any) on why certain implementations are faster or slower that others.

2. Extend testSorting.h and include two functions: fill_ascending and fill_descending, which populate an array with numbers in ascending and descending order, respectively. Then, extend function runSorting for running the algorithms considering these two kind of arrays. Plot these results in another graph.

3. Extend sorting.h and include other sorting algorithms as heapsort, quicksort, and mergesort. Then, extend function runSorting for running these algorithms. Plot these results in another graph.