Write a program to test the following sorting algorithms to sort an array (you can use the header file from textbook): (a) Quick sort

(b) Heap sort

(c) Merge sort

- Test your program on a list of 1,000 elements and on a list of 10,000 elements (randomly generated).

- Report your results in a table that shows the number of comparisons and the number of item movements for each sorting algorithm (a table for each list).

- Below is the header file from the textbook

//************************ sorts3.h *************************** // Generic sorting algorithms // overloading of < and = required

//conflict with , //template //inline void swap (T& e1, T& e2) { // T tmp = e1; e1 = e2; e2 = tmp; //}

template void insertionsort(T data[], const int n) { for (int i = 1, j; i < n; i++) { T tmp = data[i]; for (j = i; j > 0 && tmp < data[j-1]; j--) data[j] = data[j-1]; data[j] = tmp; } }

template void selectionsort(T data[], const int n) { for (int i = 0, least, j; i < n-1; i++) { for (j = i+1, least = i; j < n; j++) if (data[j] < data[least]) least = j; swap(data[least],data[i]); } }

template void bubblesort(T data[], const int n) { for (int i = 0; i < n-1; i++) for (int j = n-1; j > i; --j) if (data[j] < data[j-1]) swap(data[j],data[j-1]); }

template void combsort(T data[], const int n) { int step = n, j, k; while ((step = int(step/1.3)) > 1) // phase 1 for (j = n-1; j >= step; j--) { k = j-step; if (data[j] < data[k]) swap(data[j],data[k]); } bool again = true; for (int i = 0; i < n-1 && again; i++) // phase 2 for (j = n-1, again = false; j > i; --j) if (data[j] < data[j-1]) { swap(data[j],data[j-1]); again = true; } }

template void Shellsort(T data[], const int n) { register int i, j, hCnt, h; int increments[20], k; // create an appropriate number of increments h for (h = 1, i = 0; h < n; i++) { increments[i] = h; h = 3*h + 1; } // loop on the number of different increments h for (i--; i >= 0; i--) { h = increments[i]; // loop on the number of subarrays h-sorted in ith pass for (hCnt = h; hCnt < 2*h; hCnt++) { // insertion sort for subarray containing every hth element of array data for (j = hCnt; j < n; ) { T tmp = data[j]; k = j; while (k-h >= 0 && tmp < data[k-h]) { data[k] = data[k-h]; k -= h; } data[k] = tmp; j += h; } } } }

template void moveDown (T data[], int first, int last) { int largest = 2*first + 1; while (largest <= last) { if (largest < last && // first has two children (at 2*first+1 and data[largest] < data[largest+1]) // 2*first+2) and the second largest++; // is larger than the first;

if (data[first] < data[largest]) { // if necessary, swap(data[first],data[largest]);// swap child and parent, first = largest; // and move down; largest = 2*first+1; } else largest = last+1; // to exit the loop: the heap property } // isn't violated by data[first]; }

template void heapsort(T data[], const int n) { int i; for (i = n/2 - 1; i >= 0; --i) // create the heap; moveDown (data,i,n-1); for (i = n-1; i >= 1; --i) { swap(data[0],data[i]); // move the largest item to data[i]; moveDown(data,0,i-1); // restore the heap property; } }

template void quicksort(T data[], int first, int last) { int lower = first+1, upper = last; swap(data[first],data[(first+last)/2]); T bound = data[first]; while (lower <= upper) { while (data[lower] < bound) lower++; while (bound < data[upper]) upper--; if (lower < upper) swap(data[lower++],data[upper--]); else lower++; } swap(data[upper],data[first]); if (first < upper-1) quicksort (data,first,upper-1); if (upper+1 < last) quicksort (data,upper+1,last); }

template void quicksort(T data[], const int n) { int i, max; if (n < 2) return; for (i = 1, max = 0; i < n; i++)// find the largest if (data[max] < data[i]) // element and put it max = i; // at the end of data[]; swap(data[n-1],data[max]); // largest el is now in its quicksort(data,0,n-2); // final position; }

template void insertionsort(T data[], int first, int last) { for (int i = first, j; i <= last; i++) { T tmp = data[i]; for (j = i; j > 0 && tmp < data[j-1]; j--) data[j] = data[j-1]; data[j] = tmp; } }

template void quicksort2(T data[], int first, int last) { if (last - first < 30) insertionsort(data,first,last); else { int lower = first+1, upper = last; swap(data[first],data[(first+last)/2]); T bound = data[first]; while (lower <= upper) { while (data[lower] < bound) lower++; while (bound < data[upper]) upper--; if (lower < upper) swap(data[lower++],data[upper--]); else lower++; } swap(data[upper],data[first]); if (first < upper-1) quicksort2(data,first,upper-1); if (upper+1 < last) quicksort2(data,upper+1,last); } }

template void quicksort2(T data[], const int n) { int i, max; if (n < 2) return; for (i = 1, max = 0; i < n; i++)// find the largest if (data[max] < data[i]) // element and put it max = i; // at the end of data[]; swap(data[n-1],data[max]); // largest el is now in its quicksort2(data,0,n-2); // final position; }

template void merge(T array1[], T temp[], int first, int last) { int mid = (first + last) / 2; int i1 = 0, i2 = first, i3 = mid + 1; while (i2 <= mid && i3 <= last) if (array1[i2] < array1[i3]) temp[i1++] = array1[i2++]; else temp[i1++] = array1[i3++]; while (i2 <= mid) temp[i1++] = array1[i2++]; while (i3 <= last) temp[i1++] = array1[i3++]; for (i1 = 0, i2 = first; i2 <= last; array1[i2++] = temp[i1++]); }

template void mergesort(T data[], T temp[], int first, int last) { if (first < last) { int mid = (first + last) / 2; mergesort(data, temp, first, mid); mergesort(data, temp, mid+1, last); merge(data, temp, first, last); } }

template void mergesort(T data[], const int n) { T *temp = new T[n]; mergesort(data,temp,0,n-1); } /* #include

template class Queue : public queue { public: T dequeue() { T tmp = front(); queue::pop(); return tmp; } void enqueue(const T& el) { push(el); } };

const int bits = 31; const int radix = 10; const int digits = 10;

template void radixsort(T data[], const int n) { register int d, j, k, factor; Queue queues[radix]; for (d = 0, factor = 1; d < digits; factor *= radix, d++) { for (j = 0; j < n; j++) queues[(data[j] / factor) % radix].enqueue(data[j]); for (j = k = 0; j < radix; j++) while (!queues[j].empty()) data[k++] = queues[j].dequeue(); } }

void bitRadixsort(long data[], const int n, int b) { int pow2b = 1; pow2b <<= b; int i, j, k, pos = 0, mask = pow2b-1; int last = (bits % b == 0) ? (bits/b) : (bits/b + 1); Queue *queues = new Queue[pow2b]; for (i = 0; i < last; i++) { for (j = 0; j < n; j++) queues[(data[j] & mask) >> pos].enqueue(data[j]); mask <<= b; pos = pos+b; for (j = k = 0; j < pow2b; j++) while (!queues[j].empty()) data[k++] = queues[j].dequeue(); } }

void inline clear(long& q) { q = -1; } int inline isEmpty(long q) { return q == -1; }

template class RadixSortNode { public: T *arr; RadixSortNode *next; };

void radixsort2(long data[], const int n) { register int d, j, k, factor, where; RadixSortNode n1, n2, *p1, *p2; n1.arr = data; n2.arr = new long[n]; for (j = 0; j < n; j++) n2.arr[j] = data[j]; long *queue = new long[n], queueHeads[radix], queueTails[radix]; p1 = n2.next = &n1; p2 = n1.next = &n2; for (d = 0, factor = 1; d < digits; factor *= radix, d++) { for (j = 0; j < radix; j++) clear(queueHeads[j]); for (j = 0; j < n; j++) { where = (p1->arr[j] / factor) % radix; if (isEmpty(queueHeads[where])) queueTails[where] = queueHeads[where] = j; else { queue[queueTails[where]] = j; queueTails[where] = j; } } for (j = 0; j < radix; j++) if (!(isEmpty(queueHeads[j]))) clear(queue[queueTails[j]]); for (j = k = 0; j < radix; j++) while (!(isEmpty(queueHeads[j]))) { p2->arr[k++] = p1->arr[queueHeads[j]]; queueHeads[j] = queue[queueHeads[j]]; } p2 = p2->next; p1 = p1->next; } if (digits % 2 != 0) // if digits is an odd number; for (d = 0; d < n; d++) data[d] = p1->arr[d]; }

class RadixsortNode { public: long *arr; RadixsortNode *next; RadixsortNode() { next = 0; } RadixsortNode(long *a, int n) { arr = new long[n]; for (int i = 0; i < n; i++) arr[i] = a[i]; next = 0; } RadixsortNode(int n) { arr = new long[n]; next = 0; } };

void bitRadixsort2(long data[], const int n, int b) { int pow2b = 1; pow2b <<= b; int d, j, k, where, pos = 0, mask = pow2b-1; int last = (bits % b == 0) ? (bits/b) : (bits/b + 1); long *queues = new long[n], *queueHeads = new long[pow2b]; long *queueTails = new long[pow2b]; RadixsortNode *n2 = new RadixsortNode(data,n), *n1 = new RadixsortNode(n); n1->arr = data; n2->next = n1; n1->next = n2; for (d = 0; d < last; d++) { for (j = 0; j < pow2b; j++) clear(queueHeads[j]); for (j = 0; j < n; j++) { where = (n1->arr[j] & mask) >> pos; if (isEmpty(queueHeads[where])) queueTails[where] = queueHeads[where] = j; else { queues[queueTails[where]] = j; queueTails[where] = j; } } mask <<= b; pos = pos+b; for (j = 0; j < pow2b; j++) if (!(isEmpty(queueHeads[j]))) clear(queues[queueTails[j]]); for (j = k = 0; j < pow2b; j++) while (!(isEmpty(queueHeads[j]))) { n2->arr[k++] = n1->arr[queueHeads[j]]; queueHeads[j] = queues[queueHeads[j]]; } n2 = n2->next; n1 = n1->next; } if (last % 2 != 0) // if bits is an odd number; for (d = 0; d < n; d++) data[d] = n1->arr[d]; }

void countingsort(long data[], const long n) { long i; long largest = data[0]; long *tmp = new long[n]; for (i = 1; i < n; i++) // find the largest number if (largest < data[i]) // in data and create the array largest = data[i]; // of counters accordingly; unsigned long *count = new unsigned long[largest+1]; for (i = 0; i <= largest; i++) count[i] = 0; for (i = 0; i < n; i++) // count numbers in data[]; count[data[i]]++; for (i = 1; i <= largest; i++) // count numbers <= i; count[i] = count[i-1] + count[i]; for (i = n-1; i >= 0; i--) { // put numbers in order in tmp[]; tmp[count[data[i]]-1] = data[i]; count[data[i]]--; } for (i = 0; i < n; i++) // transfer numbers from tmp[] data[i] = tmp[i]; // to the original array; } */ #end