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 non-commercial use only.