Spring Quarter 2003 / Class webpage
// 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, firstname.lastname@example.org) // ===============================================================
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:
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.
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
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.