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.
© Computer Science Department NSU.
Permission granted for noncommercial use only.
