排序算法 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.
