Question

c++ program that finds the number of comparisons of 1000 random numbers using  bubble, insertion, quick, shell, selection, and merge sort.

Answer 1

#include <iostream>

#include <cstdlib>

using namespace std;

void swapBubble(int *xp, int *yp);

int bubbleSort(int nums[], int n);

int insertionSort(int nums[], int n);

int partition(int nums[], int low, int high, int &nCompares);

void quickSort(int arr[], int low, int high, int &nCompares);

int shellSort(int nums[], int n);

int selectionSort(int nums[], int n);

int mergeUtil(int nums[], int n, int first, int mid, int last);

int mergeSort(int nums[], int n, int first, int last);

int main()

{

// generate 1000 random numbers between 1000 and 2000

int numsBubble[1000];

int numsInsertion[1000];

int numsQuick[1000];

int numsShell[1000];

int numsSelection[1000];

int numsMerge[1000];

int size = 10;

for(int i = 0; i < 1000; i++)

{

int v = rand() % 2000 + 1000;

numsBubble[i] = v;

numsInsertion[i] = v;

numsQuick[i] = v;

numsShell[i] = v;

numsSelection[i] = v;

numsMerge[i] = v;

}

// BUBBLE SORT

cout << "Number of comparisons for Bubble sort = " << bubbleSort(numsBubble, size);

// INSERTION SORT

cout << endl << "Number of comparisons for Insertion sort = " << insertionSort(numsInsertion, size);

// QUICK SORT

int nComparesQuickSort = 0;

quickSort(numsQuick, 0, size - 1, nComparesQuickSort);

cout << endl << "Number of comparisons for Quick sort = " << nComparesQuickSort;

// SHELL SORT

cout << endl << "Number of comparisons for Shell sort = " << shellSort(numsShell, size);

// SELECTION SORT

cout << endl << "Number of comparisons for Selection sort = " << selectionSort(numsSelection, size);

// MERGE SORT

cout << endl << "Number of comparisons for Merge sort = " << mergeSort(numsMerge, size, 0, size - 1);

}

int bubbleSort(int nums[], int n)

{

int i, j;

int temp;

int nCompares = 0;

for (i = 0; i < n - 1; i++)

{

for (j = 0; j < n - i - 1; j++)

{

nCompares++;

if(nums[j] > nums[j + 1])

swapBubble(&nums[j], &nums[j+1]);

}

}

return nCompares;

}

void swapBubble(int *xp, int *yp)

{

int temp = *xp;

*xp = *yp;

*yp = temp;

}

int insertionSort(int nums[], int n)

{

int i, j, temp;

int nCompares = 0;

for(i = 1; i < n; i++)

{

j = i;

nCompares++;

while ((j > 0) && (nums[j - 1] > nums[j]))

{

if(nums[j - 1] > nums[j])

nCompares++;

temp = nums[j - 1];

nums[j - 1] = nums[j];

nums[j] = temp;

j--;

}

}

return nCompares;

}

int partition(int nums[], int low, int high, int &nCompares)

{

int pivot = nums[high];

int i = (low - 1);

for (int j = low; j <= high- 1; j++)

{

nCompares++;

if (nums[j] <= pivot)

{

i++;

swapBubble(&nums[i], &nums[j]);

}

}

swapBubble(&nums[i + 1], &nums[high]);

return (i + 1);

}

void quickSort(int nums[], int low, int high, int &nCompares)

{

if (low < high)

{

int pi = partition(nums, low, high, nCompares);

quickSort(nums, low, pi - 1, nCompares);

quickSort(nums, pi + 1, high, nCompares);

}

}

int shellSort(int nums[], int n)

{

int nCompares = 0;

for (int gap = n/2; gap > 0; gap /= 2)

{

nCompares++;

for (int i = gap; i < n; i += 1)

{

nCompares++;

int temp = nums[i];

int j;

for (j = i; j >= gap && nums[j - gap] > temp; j -= gap)

{

nums[j] = nums[j - gap];

nCompares++; // comparison for if j >= gap

nCompares++; // comparison for if temp < arr[j - gap]

}

nums[j] = temp;

}

}

return nCompares;

}

int selectionSort(int nums[], int n)

{

int i, j, temp, minIndex, first, last, second;

int nCompares = 0;

minIndex = first;

for (i = 0; i < n; i++)

{

nCompares++;

for(j = first + 1; j < last; j++)

{

nCompares++;

if(nums[j] < nums[minIndex])

minIndex = j;

nCompares++;

}

temp = nums[first];

nums[first] = nums[second];

nums[second] = temp;

}

return nCompares;

}

int mergeUtil(int nums[], int n, int first, int mid, int last)

{

int nCompares = 0;

int first1 = first, last1 = mid;

int first2 = mid + 1, last2 = last;

int temp[n - 1];

int index = first1;

while(first1 <= last1 && first2 <= last2)

{

if(nums[first1] < nums[first2])

{

temp[index] = nums[first1++];

nCompares++;

}

else

{

temp[index] = nums[first2++];

index++;

nCompares++;

}

}

while(first1 <= last1)

temp[index++] = nums[first1++];

while(first2 <= last2)

temp[index++] = nums[first2++];

for(index = first; index <= last; index++)

nums[index] = temp[index];

return nCompares;

}

int mergeSort(int nums[], int n, int first, int last)

{

int nCompares = 0;

if(first < last)

{

int mid = (first + last) / 2;

nCompares += mergeSort(nums, n, first, mid);

nCompares += mergeSort(nums, n, mid + 1, last);

nCompares += mergeUtil(nums, n, first, mid, last);

}

return nCompares;

}

***************************************************************** SCREENSHOT **********************************************************