排序算法Sorting Algorithm按顺序排列给定的数据。几乎在每个应用程序中都使用了几种排序技术来有效处理多种请求。本次作业将实现Shell Sort和Adaptive sort算法，同时计算每个所花费的时间，并绘制为折线图以进行直观比较。
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.
- project4.cpp - for autograding that uses array of short integers
- project4_long.cpp - for review by grader and uses array of long integers
- Report with plot.
Constraints
- You are allowed to use only the libraries given in the sampleMainP4.cpp.
- You need to work individually in this project.
- Any use of internet’s resources need to be cited in your code.