Question

Please write C++ code

Description:

As a senior software engineer, I would like to determine and prove which sorting algorithm is the most efficient between quick sort, merge sort, and heap sort so that I can recommend it to the development team for inclusion in the code base of an upcoming code optimization project.

Acceptance Criteria:

Well documented, executable C++ source files including classes for each of the aforementioned sorting algorithms. In addition, each sorting algorithm class implementation should be written in its own .cpp file and each class declaration should be written in its own .h file. For example, you should have a class called MergeSort and its implementation should be written in mergeSort.cpp and its declaration should be written in mergeSort.h.

The program should run test cases against each sorting algorithm using arrays of random numbers. The sizes of the arrays are the following: 10, 100, 1000, 10,000 and 100,000.

To insure a fair comparison, the same set of random numbers should be used for each sorting algorithm.

The program should produce the following chart and populate it with the computed results (Note: you do not need to have borders for the table but the output should be tabbed to insure its readability:

	Quick Sort		Merge Sort		Heap Sort
Array Size	# of Comparisons	Time to Sort	# of Comparisons	Time to Sort	# of Comparisons	Time to Sort

Time to sort is the amount of time it took to sort the arrays. You should probably use the time.h library. Number (#) of comparisons is the total number of comparisons made to sort the array. Note: every time a comparison is made you should account for it.

Provide your analysis of which sorting algorithm you would recommend based on your findings. For example, you could say: “I recommend heap sort for larger sets of numbers but I recommend quick sort for really small number sets”