Sorting Efficiency

Do a comparison of a slow sort with Big O(n2) (selection sort, insertion sort, or bubble sort) and one faster sort of Big O(n * log n) (mergesort or quicksort). Count the number of moves (a swap counts as one move). With mergesort, you can count the range of the part of the array you are sorting (i.e. last-first+1). Use the code from the textbook (copy from the lecture notes) and put in an extra reference parameter for the count.

The array needs to be 10,000 items and the number of digits should be 4. Use the srand function to set the seed and rand function to generate the numbers (use the BubbleSort support code from the Examples, chapter 11). For instance:

srand(seed);

for (int x = 0; x < 10000; x++)
  ary[x] = rand() % 10,000;

Would fill the array. Note: do NOT use the "srand(time(NULL)):". You need to recreate the array to be resorted yet again. Note: you can use the sortSupport code on Canvas.

Call the slow sort first, print out the number of moves and the first 10 and last 10 values, fill the array again using the same seed, call the fast sort, and print the number of moves and the first 10 and last 10 values.

The run would look like:

The seed to use is: 39

Bubble sort had 25349145 swaps
The first 10 values: 0 0 0 3 3 6 6 7 7 9
The last 10 values: 9991 9991 9991 9992 9992 9994 9997 9997 9998 9998

Merge sort had 133616 moves
The first 10 values: 0 0 0 3 3 6 6 7 7 9
The last 10 values: 9991 9991 9991 9992 9992 9994 9997 9997 9998 9998

Put in the radix sort as a third comparison using arrays.