Analysis of Algorithms : An Active Learning Approach

102 SORTING ALGORITHMS

c. Shellsort

d. Radix sort

e. Heapsort

f. Merge sort

g. Quicksort

3.10 Programming Exercises

You can test the complexity of a sorting algorithm in the following way:

• Write a function or functions that will do the sorting algorithm.


• Put in two global counters called compareCount and swapCount. The
  first should be incremented before every comparison of list values in every
  routine. The second should be incremented whenever list elements are
  exchanged or moved.


• Write a main program with a loop that generates a random list and then
  sorts it. In each pass of this loop, you should keep track of the maximum,
  minimum, and total values for both compareCount and swapCount. A t
  the end, you can report the overall maximum, minimum, and averages for
  these two counters. The more times you perform this loop, the more accu-
  rate your results will be.


• If you are trying to compare sort routines, you should run them on the same
  list or lists. The easiest way to do this is to have a set of counters for each
  sort, and then when you generate a random list, make a copy of the list to
  pass into each sort. You would then run all of the sorts on the first list before
  generating the next list.

1. Use the technique above with insertion sort and bubble sort. Even though
   both are O(N^2 ) sorts, does your test show any differences? How do your
   results relate to the analysis done in this chapter? Try to explain any differ-
   ences.


2. Use the technique above with heapsort, merge sort, and quicksort. Even
   though all are O(N lg N) sorts on average, does your test show any differ-
   ences? How do your results relate to the analysis done in this chapter? Try to
   explain any differences.


3. Use the technique above with the version of bubble sort given in the chap-
   ter and one or more of the versions described in the exercises in Section