Question

Write a C++ program to compare those two searching algorithms and also compare two sorting algorithms. You need to modify those codes in the book/slides to have some counters to count the number of comparisons and number of swaps. In the main function, you should have an ordered array of 120integers in order to test searching algorithms, and the other two identical arrays of 120integers not in order to test sorting algorithms. Display all counters in the main functions.Counter for number of comparisons in linear search Counter for number of comparisons in binary search Counter for number of comparisons in bubble sort Counter for number of swaps in bubble sort Counter for number of comparisons in selection sort Counter for number of swaps in selection sort“modify those codes in the book/slides” means adding additional parameters for counters, and a few statements for increasement of counters. DO not delete any statement or change return type from the original functions.No output in searching and sorting functions No global variables are allowed except for constants.

Answer 1

Answer:

A c++ program to compare those two searching and also compare two sorting algorthims

C++ Code:

#include <bits/stdc++.h>
using namespace std;
void swap(int xp, int yp)
{
int temp = *xp;
xp = yp;
*yp = temp;
}

// A function to implement bubble sort
void bubbleSort(int arr[], int n, int &cmp, int &swaps)
{
swaps = cmp = 0;
int i, j;
for (i = 0; i < n - 1; i++)

// Last i elements are already in place
for (j = 0; j < n - i - 1; j++) {
cmp++;
if (arr[j] > arr[j + 1]) {
swaps++;
swap(&arr[j], &arr[j + 1]);
}
}
}

void selectionSort(int arr[], int n, int &cmp, int &swaps)
{
int i, j, min_idx;
swaps = cmp = 0;

// One by one move boundary of unsorted subarray
for (i = 0; i < n - 1; i++)
{
// Find the minimum element in unsorted array
min_idx = i;
for (j = i + 1; j < n; j++) {
cmp++;
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}

// Swap the found minimum element with the first element
swaps++;
swap(&arr[min_idx], &arr[i]);
}
}

int binarySearch(int arr[], int l, int r, int x, int &cmp)
{
cmp = 0;
while (l <= r) {
int m = l + (r - l) / 2;
cmp++;
// Check if x is present at mid
if (arr[m] == x)
return m;

// If x greater, ignore left half
if (arr[m] < x)
l = m + 1;

// If x is smaller, ignore right half
else
r = m - 1;
}

// if we reach here, then element was
// not present
return -1;
}

int linearSearch(int arr[], int n, int x, int &cmp)
{
cmp = 0;
int i;
for (i = 0; i < n; i++) {
cmp++;
if (arr[i] == x)
return i;
}
return -1;
}

int main()
{

int cmp = 0, swaps = 0;
int array1[120], array2[120], array3[120];

for (int i = 0; i < 120; ++i)
array1[i] = i;

srand(time(NULL));

// assigning random values to array2 and array 3
for (int i = 0; i < 120; ++i)
{
array2[i] = array3[i] = rand() % 1000;
}

// searching number present at index 93
linearSearch(array1, 120, array1[110], cmp);
cout << "Number of comparisions in Linear Search: " << cmp << endl;
// searching number present at index 93
binarySearch(array1, 0, 119, array1[110], cmp);
cout << "Number of comparisions in Binary Search: " << cmp << endl;

bubbleSort(array2, 120, cmp, swaps);
cout << "Number of comparisions in Bubble Sort: " << cmp << endl;
cout << "Number of swaps in Bubble Sort: " << swaps << endl;

selectionSort(array3, 120, cmp, swaps);
cout << "Number of comparisions in Selection Sort: " << cmp << endl;
cout << "Number of swaps in Selection Sort: " << swaps << endl;
return 0;
}

Output: