LAB 10:  Due 11:59 pm, Wed Dec 1

Submit the link to your project to Moodle before the deadline. Do Not modify after the deadline.

In this lab you are going to implement various sorting algorithms we discussed. You will also compare their performances.
Create an integer array of size 5,000. Fill in the array with random numbers. Apply each of the following sorting algorithms to sort the array

       Bubble Sort
       Selection Sort
       Insertion Sort
       Shell Sort
       Merge Sort
       Quick Sort with pivot as the middle element
       Quick Sort with pivot as the median of the first, last and middle elements of the array
       Quick Sort with pivot as a random element of the array (use the rand function to choose a random arrray index)

Before applying each algorithm, initilaize the array to the original state (randomly filled values) by saving a copy of the original array. After applying each sort function print out the first 20 elements of the array to make sure that it is really sorted (your sort algorithm is working correctly).
Also measure and report the (CPU) time each algorithm takes. (This is related to Programming Exercise 9 on pages 596 in the book). More info here about timing a piece of code. Save the output in a file (in addition to sending it to the screen). Make sure you have a good user interface (do not ask too many questions!) with output in a nice, easy-to-read format. At the end, summarize the running times of all algorithms on all array sizes in a nice tabular form.

Repeat this process for arrays of size i* 5,000 for i =1, 2, 4, 6.