Simulate the performances of different sorting algorithms with randomly generated input data and measure their execution time.

Input:

Randomly generated positive integers (ranges from 0 to 100000). The numbers of input should be 1000, 5000, 10,000, 50,000 and 1000,000 which will be stored into one dimensional array. Each sorting algorithm will use the same input.

Algorithms:

• Insertion Sort

• Shellsort – For increment sequence, use sequence suggested by Shell hk = floor(hk+1/2).

• Heapsort - Use O(NlogN) algorithm

• Quicksort – Use Median-of-Three Partitioning.

Output:

Run each algorithm and print out the following results:

1. Print out the running time of algorithms for each input data and draw a graph for the running times..

2. Print out the number of swaps for each algorithm.

NOTE: If the run time of an algorithm is more than 10 mins, stop running of the algorithm.

**Subject Computer Science Data Structures and Algorithms**