Laboratory: Insertion -vs- Quick
The source file lab2.cpp contains code for both insertion and quick
sorts. One fundamental method of comparing sorts is to look at the
number of times two array values are compared. We know that Insertion
Sort is O(N2), where N is the number of elements in the
array, and Quick Sort is O(N log2N).
This program asks the user for a random seed. That is a positive
integer to start out the random number generator "rand()"
at a "random" value. The header file "stdlib.h"
is needed for the seed function "srand()" and the function
that generates random integers "rand()". It loads the
array with 1000 random integers. We use a "temp"orary
array to be sorted so that we are sorting a "sorted" array
after the insertion sort.
The program prints out the number of elements sorted followed by
the number of comparisons made for the insertion sort and the quick
Modify the program to answer the following questions and hand in
the answers on a separate sheet of paper with your name and the
answers clearly marked.
Using the last four digits of your social security number as the
seed, do the following:
- (10 points) What is your seed.
- (30 points) Run the program to sort the first 100, 200, 300,
, 900, then 1000 elements of the array. What are the comparison
- (30 points) Run the sorting between 5 and 30 elements of the
array. You will notice that the number of insertions compare values
is less than the number of quick values. That is, insertion sort
is actually more efficient than quick sort for most some small
values of an array to be sorted. What is the largest value where
the number of compares for insertion sort is smaller than the
number of compares for quick sort?
- (30 points) Explain mathematically why this is the case.
© Computer Science Department NSU.
Permission granted for non-commercial use only.