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

// ===============================================================```

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