### CSC 372 Laboratory:  Comparing Insertion and Quick Sorts

File needed: lab4.cpp

Lab4.cpp is a program that compares and contrasts the number of array comparisons used in an insertion sort and a quick sort. We use the vector class of the STL here.

The program asks for a seed to run the random number generator. Give it your student id number.

The constant SIZE in "main" gives the size of the array. Quick sort is an O(N*lgN) algorithm while insertion sort is an O(N*N) algorithm.

Write out the number of comparisons for each of the sorts for the following array sizes:

 SIZE of the array Number of comparisons for Insertion Sort Number of comparisons for Quick Sort 10 20 30 40 50 60 70 80 90 100 1000 2000

For what array sizes does insertion sort actually have a smaller number of comparisons than quick sort? ____________________________________________________

Why would this be the case?

Notice that the pivot chosen in the QSort function is the middle element of the array between first and last. Would the calculations be faster if you chose the pivot to be the median element: that is, the middle value of the three values - arr[first], arr[middle], arr[last]? Fill the table below there the second column for middle pivot is the same last three values in the second column above:

 100 Pivot as middle element Pivot as median 1000 2000

Comment on your results.