In this assignment, you will compare the performance of four sorting algorithms on two different tasks: sorting real-time (incremental) data, and sorting static data. You will prepare a report on your experience. The sorting algorithms to compare are:

• Insertion Sort

• Selection Sort

• Merge Sort

• Quick Sort

 

Sorting real-time (incremental) data : you need to generate actual size of array all at one time.

Sorting static data: Your program feeds one array element at a time from the randomly generated array to a given sorting algorithm, which is expected to keep a sorted version of all numbers that have already been given to it.

 

1. Your algorithm will work as follows:

1. Generate a random array of given size (see testing below)
2. Perform incremental sorting of this array using each algorithm given
3. Measure the time it takes for each algorithm to sort the array in milliseconds (or higher resolution)
4. Before you call each sorting algorithm, you must make copy of the array to be sorted to avoid “cheating” by re-sorting an already sorted array.

2. Static sorting:

1. Your program will sort the randomly generated array using each sorting algorithm.

3. Incremental sorting:

1. Your program feeds one array element at a time from the randomly generated array to a given sorting algorithm, which is expected to keep a sorted version of all numbers that have already been given to it.
2. You will have to modify each sorting algorithm such that they accept one element that is inserted into the end of the already sorted array, then resort the entire array.
3. There is an exception:

1. Modify insertion (Incremental-Insertion-Sort) sort such that it only executes the inside loop (placing the last element into its proper place).

4. Report:

1. Prepare a report (preferably in MS Word, Postscript, or PDF format) that contains

1. i) the output of your program (as described above)
2. ii) two charts of the output of your program (one for each task)

iii) an explanation of the results, detailing why the sorting algorithms did better/worse than the others on the two tasks

Testing:

1. You will run experiments with arrays of four sizes: 100, 1000, 10000 and 100000 elements
2. The arrays’ elements will have values between 0 and 9999 (integer)
3. You will run 30 experiments for each array size using each sorting algorithm, and plot the average run times on two charts, one for each task: Incremental and Static sorting

Program Input:

1. Your program takes no input, as all data are generated by your program

Program Output:

1. The average running times over the 30 runs for each algorithm on each of the two tasks.
2. E.g.:

Incremental sorting:

Insertion sort: 2.5 ms

Static sorting:

Insertion sort: 3.5 ms

Your program will be granted based on the following criteria:

• Implementation of Insertion Sort 
• Implementation of Selection Sort 
• Implementation of Insertion Sort 
• Implementation of Quick Sort
• Report 
• Quality of code and comments 
• You need to fill this table according to instructions.

	Insertion Sort	Selection Sort	Merge Sort	Quick Sort
Static	A[100] 30 experiments A[1000] 30 experiments A[10000] 30 experiments A[100000] 30 experiments	A[100] 30 experiments A[1000] 30 experiments A[10000] 30 experiments A[100000] 30 experiments	A[100] 30 experiments A[1000] 30 experiments A[10000] 30 experiments A[100000] 30 experiments	A[100] 30 experiments A[1000] 30 experiments A[10000] 30 experiments A[100000] 30 experiments
Incremental	A[100] 30 experiments A[1000] 30 experiments A[10000] 30 experiments A[100000] 30 experiments	A[100] 30 experiments A[1000] 30 experiments A[10000] 30 experiments A[100000] 30 experiments	A[100] 30 experiments A[1000] 30 experiments A[10000] 30 experiments A[100000] 30 experiments	A[100] 30 experiments A[1000] 30 experiments A[10000] 30 experiments A[100000] 30 experiments

• • You need to plot the average run times on two charts, one for each task: Incremental and Static sorting.