Question

C++!!!

PLEASE PAY ATTENTION TO THE BOLD TEXT VERY WELL. THANK YOU

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.

Please use the file names listed below since your file will have the following components:

Ch18_Ex15.cpp

searchSortAlgorithms.h

Answer 1

Code:

Ch18_Ex15.cpp

Code as text:

#include <iostream>

#include <cstdlib>

#include "searchSortAlgorithms.h"

using namespace std;

#define size 5000

// function to create three identical arrays

// elements range from 0 - 10000

void CreateList(int A[], int B[], int C[]) {

for (int i = 0; i < size; i++) {

A[i] = rand() % 10000;

B[i] = A[i];

C[i] = B[i];

}

}

int main() {

// declare three lists

int list1[size], list2[size], list3[size];

// create list using function

CreateList(list1, list2, list3);

// variables to count comparisons and assignments

int noOfComparisions, noOfAssignments;

// sort and output the result

cout << "Sorting list1 using bubble sort\n";

BubbleSort(list1, size, noOfComparisions, noOfAssignments);

cout << "Number of comparisons: " << noOfComparisions << endl;

cout << "Number of item assignments: " << noOfAssignments << endl;

cout << "\nSorting list2 using selection sort\n";

SelectionSort(list2, size, noOfComparisions, noOfAssignments);

cout << "Number of comparisons: " << noOfComparisions << endl;

cout << "Number of item assignments: " << noOfAssignments << endl;

cout << "\nSorting list3 using insertion sort\n";

InsertionSort(list3, size, noOfComparisions, noOfAssignments);

cout << "Number of comparisons: " << noOfComparisions << endl;

cout << "Number of item assignments: " << noOfAssignments << endl;

return 0;

}

searchSortAlgorithms.h

Code as text:

#ifndef _SEARCHSORTALGORITHMS_

#define _SEARCHSORTALGORITHMS_

using namespace std;

// function to sort using bubble sort

void BubbleSort(int arr[], int n, int &comp, int &assg) {

comp = assg = 0;

int i, j;

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

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

comp++; // increase comp by 1

if (arr[j] > arr[j+1]) {

int temp = arr[j];

arr[j] = arr[j+1];

arr[j+1] = temp;

assg += 3; // 3 assignments

}

}

}

}

// function to sort using selection sort

void SelectionSort(int arr[], int n, int &comp, int &assg) {

comp = assg = 0;

int i, j, min_idx;

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

min_idx = i;

assg++; // 1 assignment

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

comp++; // 1 comparison

if (arr[j] < arr[min_idx]) {

min_idx = j;

assg++; // 1 assignment

}

}

int temp = arr[min_idx];

arr[min_idx] = arr[i];

arr[i] = temp;

assg += 3; // 3 assignments

}

}

// function to sort using insertion sort

void InsertionSort(int arr[], int n, int &comp, int &assg) {

comp = assg = 0;

int i, key, j;

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

key = arr[i];

j = i - 1;

assg += 2; // 2 assignments

comp += 2; // 2 comparisons

while (j >= 0 && arr[j] > key) {

arr[j + 1] = arr[j];

j = j - 1;

assg += 2; // 2 assignments

}

arr[j + 1] = key;

assg++; // 1 assignment

}

}

#endif

Sample run: