Question

Write a 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 120 integers 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.

--------------------------------------------------

//*****************************************************************
// The linearSearch function performs a linear search on an       *
// integer array. The array arr, which has a maximum of size      *
// elements, is searched for the number stored in value. If the   *
// number is found, its array subscript is returned. Otherwise,   *
// -1 is returned indicating the value was not in the array.      *
//*****************************************************************

int linearSearch(const int arr[], int size, int value)
{
   int index = 0;       // Used as a subscript to search array
   int position = -1;   // To record position of search value
   bool found = false; // Flag to indicate if the value was found

   while (index < size && !found)
   {
      if (arr[index] == value) // If the value is found
      {
         found = true;         // Set the flag
         position = index;     // Record the value's subscript
      }
      index++;                  // Go to the next element
   }
   return position;              // Return the position, or -1
}

------------------------------------------------------------------------

//***************************************************************
// The binarySearch function performs a binary search on an     *
// integer array. array, which has a maximum of size elements, *
// is searched for the number stored in value. If the number is *
// found, its array subscript is returned. Otherwise, -1 is     *
// returned indicating the value was not in the array.          *
//***************************************************************

int binarySearch(const int array[], int size, int value)
{
   int first = 0,             // First array element
       last = size - 1,       // Last array element
       middle,                // Mid point of search
       position = -1;         // Position of search value
   bool found = false;        // Flag

   while (!found && first <= last)
   {
      middle = (first + last) / 2;     // Calculate mid point
      if (array[middle] == value)      // If value is found at mid
      {
         found = true;
         position = middle;
      }
      else if (array[middle] > value) // If value is in lower half
         last = middle - 1;
      else
         first = middle + 1;           // If value is in upper half
   }
   return position;
}

---------------------------------------------------------------

//*****************************************************************
// The bubbleSort function sorts an int array in ascending order. *
//*****************************************************************
void bubbleSort(int array[], int size)
{
   int maxElement;
   int index;

   for (maxElement = size - 1; maxElement > 0; maxElement--)
   {
      for (index = 0; index < maxElement; index++)
      {
         if (array[index] > array[index + 1])
         {
            swap(array[index], array[index + 1]);
         }
      }
   }
}

//***************************************************
// The swap function swaps a and b in memory.       *
//***************************************************
void swap(int &a, int &b)
{
   int temp = a;
   a = b;
   b = temp;
}

-------------------------------------------------------------------------------------------

//********************************************************************
// The selectionSort function sorts an int array in ascending order. *
//********************************************************************
void selectionSort(int array[], int size)
{
   int minIndex, minValue;

   for (int start = 0; start < (size - 1); start++)
   {
      minIndex = start;
      minValue = array[start];
      for (int index = start + 1; index < size; index++)
      {
         if (array[index] < minValue)
         {
            minValue = array[index];
            minIndex = index;
         }
      }
      swap(array[minIndex], array[start]);
   }
}

//***************************************************
// The swap function swaps a and b in memory.       *
//***************************************************
void swap(int &a, int &b)
{
   int temp = a;
   a = b;
   b = temp;
}

Please comment in all-new lines of code, thank you

Answer 1

#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 Screenshot:-

-----------------------------------

Please give me a UPVOTE. Thank you :)