CSC 372
Laboratory:  Insertion -vs- Quick

Uses

• lab2.cpp

Background

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(N²), where N is the number of elements in the array, and Quick Sort is O(N log₂N).

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 sort.

Requirements:

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:

1. (10 points) What is your seed.
2. (30 points) Run the program to sort the first 100, 200, 300, …, 900, then 1000 elements of the array. What are the comparison values?
3. (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?
4. (30 points) Explain mathematically why this is the case.
   

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