What I got so far

Do a comparison of a slow sort with Big O(n²) (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 Moodle.

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

For 10 extra credit points, put in the radix sort as a third comparison using arrays.

#include

#include

using namespace std;

typedef int DataType;

void bubbleSort(DataType[], int);

void swap(DataType&, DataType&);

void mergeSort(DataType[], int, int);

void merge(DataType[], int, int, int);

void radix(DataType[], int, int, int);

const int SIZE = 10000;

int count = 0;

int main()

{

int seed = 39;

int theArray[SIZE];

srand(seed);

for (int i = 0; i < SIZE; i++) { theArray[i] = rand() % SIZE; }

bubbleSort(theArray, SIZE);

cout << "The seed to use is: " << seed << endl; cout << "Bubble Sort had " << count << " swaps." << endl; cout << "The 10 values are: "; for (int i = 0; i < 10; i++) { cout << theArray[i] << " "; } cout << " The last 10 values are: "; for (int i = SIZE - 10; i < (SIZE); i++) { cout << theArray[i] << " "; } cout << " " << endl;

mergeSort(theArray, 0, SIZE - 1);

cout << "Merge Sort had " << count << " swaps." << endl; cout << "The 10 values are: "; for (int i = 0; i < 10; i++) { cout << theArray[i] << " "; }

cout << " The last 10 values are: "; for (int i = SIZE - 10; i < (SIZE); i++) { cout << theArray[i] << " "; }

cout << " " << endl;

system("PAUSE"); return 0; }

void bubbleSort(DataType theArray[], int n) { bool sorted = false; for (int pass = 1; (pass < n) && !sorted; ++pass) { sorted = true; for (int index = 0; index < n - pass; ++index) { int nextIndex = index + 1; if (theArray[index] > theArray[nextIndex]) { swap(theArray[index], theArray[nextIndex]); count++; sorted = false; } } } }

void swap(DataType& x, DataType& y) { DataType temp = x; x = y; y = temp; }

void mergeSort(DataType theArray[], int first, int last) { if (first < last) { int mid = ((first + last) / 2); mergeSort(theArray, first, mid); mergeSort(theArray, mid + 1, last); merge(theArray, first, mid, last); } }

void merge(DataType theArray[], int first, int mid, int last) { DataType tempArray[SIZE]; int first1 = first; int last1 = mid; int first2 = mid + 1; int last2 = last; int index = first1;

for (; (first1 <= last1) && (first2 <= last2); ++index) { if (theArray[first1] < theArray[first2]) { tempArray[index] = theArray[first1]; ++first1; } else { tempArray[index] = theArray[first2]; ++first2; } } for (; first1 <= last1; ++first1, ++index) { tempArray[index] = theArray[first]; } for (; first2 <= last2; ++first2, ++index) { tempArray[index] = theArray[first2]; } for (index = first; index <= last; ++index) { theArray[index] = tempArray[index]; } }

void radix(int theArray[], int n) { // Find the maximum number to know number of digits int m = getMax(theArray, n);

for (int exp = 1; m / exp > 0; exp *= 10) count(theArray, n, exp); }