Example Sort Algorithms  

Exercises.

1. These two "sort" algorithms have been equipped with extra code designed to measure the number of comparisons that are made during a run (code highlighted in red).

a. Explain why the number of comparisons is a measure of the runtime of each of the algorithms.

b. Do you agree with the placement of the measurement code capturing every call to the type T less-than operator?

2. Write a C++ driver program for running sorts on unsigned long data in input files. Run the sort tests on files of unsigned integers of size 10, 100, and 1000.

a. For random data, what is the number of comparisons, approximately?

b. For data that is already sorted, what are the results?

c. What would you expect the number of comparisons called by these two algorithms to be, on (a) random data and (b) sorted data?

template void SelectionSort (T *array, size t size) if (size void InsertionSort (T* array, size t size) if (size