CS 202 Homework 1 – Algorithm Efficiency and Sorting

Question 1 – 15 points
(a) [5 points] Show that    ( )

values in Big-O definition

is
(    )

by specifying appropriate c and n0

    (b) [10 points] Trace the following sorting algorithms to sort the array [ 24, 8, 51, 28, 20, 29, 21, 17, 38, 27 ] in ascending order. Use the array implementation of the algorithms as described in the textbook and show all major steps.

        ◦ Insertion sort

        ◦ Bubble sort


Question 2 – 70 points

Implement the following functions in the sorting.cpp file:

    (a) [40 points] Implement the selection sort, merge sort, quick sort, and radix sort algorithms. Your functions should take an array of integers and the size of that array and then sort it in ascending order. Add two counters to count and return the number of key comparisons and the number of data moves for all sorting algorithms except the radix sort. For the quick sort algorithm, you are supposed to take the first element of the array as pivot. Your functions should have the following prototypes (all prototypes should be in sorting.h):


void selectionSort(int *arr, const int size, int &compCount, int &moveCount); void mergeSort(int *arr, const int size, int &compCount, int &moveCount); void quickSort(int *arr, const int size, int &compCount, int &moveCount); void radixSort(int *arr, const int size);


For key comparisons, you should count each comparison like k1 < k2 as one comparison, where k1 and k2 correspond to the value of an array entry (that is, they are either an array entry like arr[i] or a local variable that temporarily keeps the value of an array entry).

For data moves, you should count each assignment as one move, where either the right-hand side of this assignment or its left-hand side or both of its sides correspond to the value of an array entry (e.g., a swap function has three data moves).

    (b) [15 points] To test your implementation and conduct the experiments described below, you must write additional auxiliary global functions as follows. The prototypes of these functions are given below. The first function displays the array items on the screen. The other ones are to create four identical arrays that will be used for testing the sorting algorithms with random numbers (generated using the random number generator function rand), numbers in ascending order, and numbers in descending order, respectively.


void displayArray(const int *arr, const int size);

void createRandomArrays(int *&arr1, int *&arr2, int *&arr3, int *&arr4, const int size); void createAscendingArrays(int *&arr1, int *&arr2, int *&arr3, int *&arr4, const int size); void createDescendingArrays(int *&arr1, int *&arr2, int *&arr3, int *&arr4, const int size);

    (c) [5 points, mandatory] Create a main.cpp file which does the following in order:

        ◦ creates an array from the following: {12, 7, 11, 18, 19, 9, 6, 14, 21, 3, 17, 20, 5, 12, 14, 8}.

        ◦ calls the selectionSort function, displays the number of key comparisons and the number of data moves to sort this array, and calls the displayArray function to show the contents of the array after selection sorting

        ◦ calls the mergeSort function, displays the number of key comparisons and the number of data moves to sort this array, and calls the displayArray function to show the contents of the array after merge sorting

        ◦ calls the quickSort function, displays the number of key comparisons and the number of data moves to sort this array, and calls the displayArray function to show the contents of the array after quick sorting

        ◦ calls the radixSort function to sort this array and calls the displayArray function to show the contents of the array after radix sorting

At the end, write a basic Makefile which compiles all of your code and creates an executable file named hw1. Check out this tutorial for writing a simple makefile:

http://www.cs.colby.edu/maxwell/courses/tutorials/maketutor/

Please make sure that your Makefile works properly, otherwise you will not get any points from Question 2.


Important: Then run your executable and add the screenshot of the console to the solution of Question 2 in the pdf submission.


    (d) [10 points] In this part, you will analyze the performance of the sorting algorithms that you will have implemented. Write a performanceAnalysis function to systematically call these algorithms. This function should call the auxiliary global functions to create the arrays with different contents. For each scenario (random, ascending, descending), use the following sizes for the arrays: 6000, 10000, 14000, 18000, 22000, 26000, 30000. Run each of the sorting algorithms with each scenario and output the elapsed time in milliseconds, the number of key comparisons and the number of data moves.


The performanceAnalysis function needs to produce an output similar to the one given on the next page. Include this output to the answer of Question 2 in the pdf submission.

-----------------------------------------------------
Analysis of Selection Sort

Array Size
Elapsed time
compCount
moveCount
6000
x
ms
x
x
10000
x
ms
x
x
...




-----------------------------------------------------
Analysis of Merge
Sort


Array Size
Elapsed time
compCount
moveCount
6000
x
ms
x
x
10000
x
ms
x
x
...




-----------------------------------------------------
Analysis of Quick
Sort


Array Size
Elapsed time
compCount
moveCount
6000
x
ms
x
x
10000
x
ms
x
x
...




-----------------------------------------------------
Analysis of Radix
Sort


Array Size
Elapsed time


6000
x
ms


10000
x
ms


...







Question 3 – 15 points

After running your programs, prepare a single page report about the experimental results that you will have obtained in Question 2. With the help of a spreadsheet program (Microsoft Excel, Matlab or other tools), plot elapsed time versus the array size for each sorting algorithm implemented in Question 2. Combine the outputs of each sorting algorithm in a single graph.

In your report, interpret and compare your empirical results with the theoretical ones. Explain any differences between the empirical and theoretical results, if any.

Do not forget to discuss how the time complexity of your program changed when you applied the sorting algorithms to already sorted arrays (ascending and descending) instead of an array containing randomly generated numbers. Also briefly explain the rationality behind this change.