C++ Data structures program

CS 5005 Computing Structures – Programming Project 4 – Fall 2019

Due December 2nd, 2019, 11:59 PM

Discussion Sorting algorithms are arranging the given data in order. Several sorting techniques are used in

almost every application to efficiently handle requests of many kinds. In this project, you would

be implementing the Shell Sort and Adaptive sort techniques. You would also be measuring the

time taken for each of them and plotting them as a line graph to visually compare.

Implementation of the class The sortData class defined in the sampleMainP3.cpp file will be used. The two fields we have

here which are private are the number of elements(N) and the elements themselves(elements)

which is an array of integers of either short or long(only for experimentation).

The methods(prototypes) that would be required for implementation of these sorting techniques

are given to you in the sampleMain file.

Generation of the random numbers for sorting You are required to generate random numbers that are numElements number long. The

numElements are given to you in the input file.

The way you would generate the random numbers is with the seed(srand()) that is given to you in

the input file. This seed would make sure the random numbers that you generate are pseudo

random. This means that with the same seed, every time you generate the numbers, it will be the

same set of numbers.

The random numbers generated also need to be within the range(between lower and upper) given

in the input file.

Input file The first line in the input file is the number of elements(numElements). The line following that

has the seed followed by the lower range and the upper range for random number generation.

Submission There will be 2 parts to the submission component in this project. To write the algorithms and

sort the pseudo randomly generated numbers so that you pass the GradeScope autograding test

cases(upload code saved as project4.cpp). The second would be to experiment and write a report

on the sorting algorithms written for an array of short and long integers. More details follow.

Autograder submission The code written for the autograding submission would be using the array of short integers. You

are given a sample output file and you would need to write the algorithms and display the sorted

numbers for the given input file. Nothing fancy here.

Experimentation and Report submission

For the experimentation part, you would change the class to having only the numElements and an

array of long integers. And you would run both the sorting algorithms to sort these array of long

integers.

You would have to plot the time taken for sorting(does not include random generation nor

printing – use clock_t) 5000, 10000, 50000, 100000 number of elements for both short and long

integers for both the algorithms(a graph(time vs numElements) with 4 lines).

You also need to explain the results you get by answering the question of why.

Final submission requirement You would need to submit 3 files at the end.

1. project4.cpp – for autograding that uses array of short integers

2. project4_long.cpp – for review by grader and uses array of long integers

3. Report with plot.

Constraints 1. You are allowed to use only the libraries given in the sampleMainP4.cpp.

2. You need to work individually in this project.

3. Any use of internet’s resources need to be cited in your code.