Question

Please answer in C++ with the correct files (in bold). Thanks!

1. Write a program that creates three identical arrays, list1, list2, and list3, of 5000 elements. The program then sorts list1 using bubble sort, list2 using selection sort, and list3 using insertion sort and outputs the number of comparisons and item assignments made by each sorting algorithm.
2. Please use the file names listed below since your file will have the following components:
   Ch18_Ex15.cpp
   searchSortAlgorithms.h

Answer 1

//Source Code:

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

void bubbleSort(int arr[], int n, int &comp, int &assignments){
assignments = 1; // by assigning i=0
for(int i=0;i<n-1;i++){
++comp; // by comparing (i<n-1)
++assignments; // by assigning j=0
for(int j=0;j<n-1-i;j++){
++comp; // by condition (j<n-1-i)
if(arr[j] > arr[j+1]){
++comp;// by comparing (arr[j] > arr[j+1])
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
assignments += 3; // by above three statements
}
++comp; // when (arr[j] > arr[j+1]) condition fails
}
++comp; // when (j<n-1-i) condition fails
}
++comp; // when (i<n-1) condition fails
}

void selectionSort(int arr[], int n, int &comp, int &assignments){
assignments = 1; // by assigning i=0
for(int i=0; i<n-1; i++){
++comp; // by condition (i<n-1)
int min = arr[i];
int pos = i;
assignments += 3; // from above two statements and from j=i+1 below
for(int j=i+1;j<n;j++){
++comp;// by comparing (j<n)
if(arr[j] < min){
++comp; // by comparing (arr[j] < min)
min = arr[j];
pos = j;
assignments += 2; // from above two statements
}
++comp; // when if condition fails
}
++comp; // when condition (j<n) fails

int temp = arr[i];
arr[i] = min;
arr[pos] = temp;
assignments += 3; // by above three statements
}
++comp; //when (i<n-1) condition fails
}

void insertionSort(int arr[],int n, int &comp, int &assignments){
int i, j, temp;
assignments = 1; // by assigning i=1
for (i = 1; i < n; i++){
++comp;// by condition (i<n)
temp = arr[i];
j = i-1;
assignments += 2; // by above two statements
while (j >= 0 && arr[j] > temp){
comp += 2; // by (j >= 0) and (arr[j] > temp)
arr[j+1] = arr[j];
j = j-1;
assignments += 2; // by above two statements
}
comp += 2; //when condition (j >= 0) and condition (arr[j] > temp) fails

arr[j+1] = temp;
assignments++; // by above statement
}
comp++; //when (i<n) condition fails
}

void fillArray(int list[], int length)
{
srand(time(0));
for (int i = 0; i < length; i++){
list[i] = rand() % 20000;
}
}

void copyArray(int list1[], int list2[], int n)
{
for (int i = 0; i < n; i++){
list2[i] = list1[i];
}
}

int main()
{
int list1[5000];
int list2[5000];
int list3[5000];

int compBubbleSort = 0, compSelectionSort = 0, compInsertionSort = 0;
int assignBubbleSort = 0, assignSelectionSort = 0, assignInsertionSort = 0;

fillArray(list1, 5000);
copyArray(list1, list2, 5000);
copyArray(list1, list3, 5000);

bubbleSort(list1, 5000, compBubbleSort, assignBubbleSort);
selectionSort(list2, 5000, compSelectionSort, assignSelectionSort);
insertionSort(list3, 5000, compInsertionSort, assignInsertionSort);

cout << "Number of comparisons---" << endl;
cout << " Bubble sort: " << compBubbleSort << endl;
cout << " Selection sort: " << compSelectionSort << endl;
cout << " Insertion sort: " << compInsertionSort << endl << endl;

cout << "Number of item assignments---" << endl;
cout << " Bubble sort: " << assignBubbleSort << endl;
cout << " Selection sort: " << assignSelectionSort << endl;
cout << " Insertion sort: " << assignInsertionSort << endl << endl;

return 0;
}

//Output Screenshot :