C++ Programming: COMPARING THREE SORTING ALGORITHMS

INTRODUCTION

We have recently described two sorting algorithms---Merge Sort and Quick Sort---whose times are, in general, O(n log n). This project implements and exercises these algorithms and an earlier algorithm whose time is O(n²). This investigation should confirm our theoretical observations about their behaviors.

DESCRIPTION

Design, implement, document, test, and exercise a program that generates a specified number of random integers, records them in three arrays, then sorts the arrays with Insertion Sort, Merge Sort, and Quick Sort, respectively. Augment the three sorting algorithms with counters and report the number of characteristic operations each performs in sorting the (same) random values.

INPUT

The program reads from the terminal the number of random integers to generate, a seed value for the pseudo-random number generator, and a character that indicates whether or not to print the unsorted and sorted values.

OUTPUT

The program reports to the terminal the numbers of executions of characteristic operations performed by each sorting algorithm and, at the user's discretion, the unsorted and sorted values themselves.

ERRORS

The program can assume that its input is as described; it need not detect any errors.

EXAMPLE

A run of the program might look like this:

 Enter the number of values to generate and sort, between 1 and 5000: 750 Enter an integer seed value: 42 Print the values? n Insertion Sort count = 145364 Merge Sort count = 14452 Quick Sort count = 7785 

Your mileage almost certainly will vary.

OTHER REQUIREMENTS

Use the program to observe how the algorithms' times, as represented by the counts of characteristic operations, increase as the number n of values being sorted grows, by running the program on several instances of several problem sizes; that is, numbers of values to sort. Do the results confirm our discussions of the algorithms' big-O times in class? Consider graphs of operation counts against problem size. Do the numbers of operations vary with the initial arrangement of the values?