1. Based upon the pseudocode studied/reviewed in class, implement the three sorting algorithms (bubble, selection and insertion sort)
2. Test the three functions, and verify that the list (implemented using vector or array) is indeeded sorted.
3. Measure the running time of the three sorting algorithms when sorting a list of ints.
4. Compare the performance of sorting algorithms: bubble sort, selection sort, insertion sort by sorting a list (implemented using array or vector) of ints.

The following example illustrates how your program should work:

 a.out : 1. Testing the three algorithms: Testing bubble sort with an array of size 10: correct! Testing selection sort with an array of size 10: correct! Testing inserion sort with an array of size 10: correct! 2. Measuring the three sorting algorithms with 30 ranondomly generated inputs Measuring running time for array of size 100 3. Summary of measurement result Input-size average running time ---------------------------------------------------------------- bubble selection Insertion 100 .... ... ... 

Details:

Here is a step-by-step guide to finish this lab:

1. Implement three helper functions for generating random list of ints, and checking if a list is sorted, and duplicate the list, respectively.

    /* Generate an vector and fill it with random integers between 1 and 10,000 return the address of the array @param size: the size of the array to be generated @return the vector */ vector GenerateRandomVector(int size); /* display the content of the vector */ void PrintVector (vector & intList); /* return true if elements in a is arranged in ascending order return false otherwise */ bool IsSorted (vector a); 

2. Test bubble sort function as below:

    vector intVector = GenerateRandomVector (10); cout <<"Sorting vector:"; PrintVector (intVector); BubbleSort (intVector); cout <<"After:"; PrintArray (intVector); if (IsSorted (intVector)) cout <<"BubbleSort passed testing!\"; else cout <<"BubbleSort does not work! "; //when intVector goes out of scope, its memory will be //deallocated by its destructor 

3. Similarly, implement and test selection sort and insertion sort.
4. (10 pts extra credits) Implement and test the three sorting algorithms recursively.