Description
You are asked to implement six sorting algorithms: bubble sort, insertion sort, selection sort,
merge sort, quick sort using extra array for partitioning, and quick sort with in-place partitioning.
They sort integers in ascending order. They are combined into a single program. Based on the
user specification, a corresponding sorting algorithm will be called.
1. Input format
You will read the sorting task from the standard input. (For the ease of testing, you can write
each test case in a file and then use Linux file redirection function “<” to read from the file.)
The first line is an integer, which specifies the sorting algorithm you should call. The integer can
take six values: 0 for bubble sort, 1 for insertion sort, 2 for selection sort, 3 for merge sort, 4 for
quick sort using extra array for partitioning, and 5 for quick sort with in-place partitioning. Other
values are illegal, but you can assume that the user will not input illegal values.
The second line specifies the number of integers you are asked to sort. Let that number be N.
Then the following N lines list the N integers to be sorted.
An example of input is
3
5
-1
-3
2
0
4
This example calls merge sort to sort 5 integers -1, -3, 2, 0, and 4 in ascending order.
2. Output Specification
Your program writes the sorted result to the standard output. Each line lists one number. For
the above example, the output looks like
-3
-1
0
2
4
III. Comparison of the Sorting Algorithms
We also ask you to study the performances of these six sorting algorithms. To do this, you
should first generate different arrays of random integers with different sizes. Then you should
apply your sorting algorithms to these arrays. Finally, you should plot a figure showing the
runtime of each algorithm versus the array size. For comparison purpose, you should plot all six
curves corresponding to the six sorting algorithms in the same figure. (You do not need to upload
the source codes for this comparison program.)
Hint:
1. You may want to write another program that calls the core sorting procedures to do this study.
2. You can use mrand48() to generate integers uniformly distributed in the range
[-2
31, 231
-1].
3. You can use clock() function to get the runtime.
4. Although the major factor that affects the runtime is the size of the input array, however, the
runtime for an algorithm may also weakly depend on the detailed input array. Thus, for each
size, you should generate a number of arrays of that size and obtain the mean runtime on all
these arrays. Also, for fair comparison, the same set of arrays should be applied to all the
algorithms.
5. You should try at least 5 representative sizes.
IV. Implementation Requirements and Restrictions
You must make sure that your code compiles successfully on a Linux operating system.
You may #include
may be included, and you may not make any call to any function in any other library.
V. Compiling and Testing
Write a Makefile. Put all your compiling commands in the Makefile. The output program
should be named main.
To make sure that the program works, you should test each sorting algorithm you write.
VI. Submitting and Due Date
You should submit all the source code files for the program described in Section II, a
Makefile, and a report of the runtime comparison of different sorting algorithms. The
Makefile compiles a program named main. The report should be in pdf format. At the end of
your report, please attach all your codes. See announcement from the TAs for details about how
to submit these files. The submission deadline is 11:59 pm on Sep. 30th, 2018.
VII. Grading
Your program will be graded along five criteria:
1. Functional Correctness
2. Implementation Constraints
3. General Style
4. Performance
5. Report on the performance study
Functional Correctness is determined by running a variety of test cases against your program,
checking your solution using our automatic testing program. We will grade Implementation
Constraints to see if you have met all of the implementation requirements and restrictions.
General Style refers to the ease with which TAs can read and understand your program, and the
cleanliness and elegance of your code. Part of your grade will also be determined by the
performance of your algorithm. We will test your program with some large test cases. If your
program is not able to finish within a reasonable amount of time, you will lose the performance
score for those test cases. Finally, we will also read your report and grade it based on the quality
of your performance study.
