Description

To give you experience in implementing various sorting algorithms

To empirically study the time efficiency of different sorting algorithms.

II. Programming Assignment

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³¹, 2³¹-1].
2. You can use clock() function to get the runtime.
3. 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.
4. 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 <iostream>, <fstream>, <sstream>, <string>,

<cstdlib>, <climits>, <ctime>, and <cassert>. No other system header files 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.