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:

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:

Comment on your results.

© Computer Science Department NSU.
Permission granted for non-commercial use only.