Write a program to test the following sorting algorithms to sort an array (you c
ID: 3815201 • Letter: W
Question
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).
- Include screenshots of different test cases with a discussion of your results.
****Below is the Header file from the textbook****
//************************ sorts.h ***************************
// Generic sorting algorithms
// overloading of < and = required
//conflict with <algorithms>, <queue>
//template<class T>
//inline void swap (T& e1, T& e2) {
// T tmp = e1; e1 = e2; e2 = tmp;
//}
template<class T>
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<class T>
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<class T>
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 <class T>
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<class T>
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<class T>
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<class T>
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<class T>
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<class T>
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<class T>
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<class T>
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<class T>
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<class T>
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<class T>
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<class T>
void mergesort(T data[], const int n) {
T *temp = new T[n];
mergesort(data,temp,0,n-1);
}
#include <queue>
template<class T>
class Queue : public queue<T> {
public:
T dequeue() {
T tmp = front();
queue<T>::pop();
return tmp;
}
void enqueue(const T& el) {
push(el);
}
};
const int bits = 31;
const int radix = 10;
const int digits = 10;
template<class T>
void radixsort(T data[], const int n) {
register int d, j, k, factor;
Queue<T> 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<long> *queues = new Queue<long>[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 T>
class RadixSortNode {
public:
T *arr;
RadixSortNode *next;
};
void radixsort2(long data[], const int n) {
register int d, j, k, factor, where;
RadixSortNode<long> 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;
}
Explanation / Answer
public class MySelectionSort {
public static int[] doSelectionSort(int[] arr)
{
for (int i = 0; i < arr.length - 1; i++)
{
int index = i;
for (int j = i + 1; j < arr.length; j++)
if (arr[j] < arr[index])
index = j;
int smallerNumber = arr[index];
arr[index] = arr[i];
arr[i] = smallerNumber;
}
return arr;
}
public static void main(String a[]){
int[] arr1 = {10,34,2,56,7,67,88,42};
int[] arr2 = doSelectionSort(arr1);
for(int i:arr2){
System.out.print(i);
System.out.print(", ");
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.