Question

In this problem you will test and analyze the following sorting algorithms: Selection, Bubble, Insertion, Merge, and Quick. You can use the code provided in the lecture slides after modifying it to meet the following requirements: 1. Analyze the algorithms by sorting, in ascending order, arrays of 1000 integers (i.e., no need to use template functions as in the lecture slides). 2. Create three arrays of 1000 integers: BST, AVG, and WST. Where a. BST has 1000 integers already sorted in ascending order (e.g., 10, 20, 30, ...etc.). b. AVG has 1000 randomly generated integers, where each integer is between 0 and 100,000. c. WST has 1000 integers sorted in reverse order (e.g., 1000, 990, 980, ...etc.). 3. Test the five sorting algorithms with three 1000‐integer arrays: tBST, tAVG, and tWST. Before testing each algorithm, these three arrays (tBST, tAVG, and tWST) must be re‐initialize as copies from BST, AVG, and WST respectively (you can write a function to carry out the copy task). This is to make sure that all algorithms are tested with an identical set of arrays.

Answer 1

1) Selection, bubble and insertion sort requires no moves in the sorted array because there will be n comparisons in the array and no swapping would take place after each comparison so zero moves.

2) Bubble and insertion sort result in 999 comparisons as we are required to iterate only one time over the array. this can be easily explained from the diagram as in bubble sort all the elements will be in their sorted position so each element will be encountered only once.

3) In selection sort, any element is compared with all the elements and accordingly smaller is paced first so in the reverse sorted array there will be at least n^2 comparisons so n^2 moves.

4) in merge sort an array is always divided into n nos of parts and then sorted so in worst case as well as best case the array will be divided so same numbers of moves.