Question

In C++

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

DO NOT USE ANSWERS THAT ALREADY BEEN POSTED, please use code from the assignment

Copy-paste will be reported

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;
}

Answer 1

#include<iostream>
#include<stdlib.h>
using namespace std;

void bubbleSort(int arr[], int n,int &count_bubbleSort,int &swap_bubbleSort)
{
   int maxElement;
   int index;

   for (maxElement = n - 1; maxElement > 0; maxElement--)
   {
      for (index = 0; index < maxElement; index++)
      {
          count_bubbleSort++;  //Counting number of comparisons in bubble sort
         if (arr[index] > arr[index + 1])
         {
             swap_bubbleSort++;     //Counting number of swaps in bubble sort
            swap(arr[index], arr[index + 1]);
         }
      }
   }
}
void selectionSort(int array[], int size,int &count_selectionSort,int &swap_slectionSort)
{
   int minIndex, minValue;

   for (int start = 0; start < (size - 1); start++)
   {
      minIndex = start;
      minValue = array[start];
      for (int index = start + 1; index < size; index++)
      {
          count_selectionSort++;    //Counting number of comparisons in selection sort
         if (array[index] < minValue)
         {
            minValue = array[index];
            minIndex = index;
         }
      }
      swap_slectionSort++;      //Counting number of swaps in selection sort
      swap(array[minIndex], array[start]);
   }
}
void swap(int &a, int &b)
{
   int temp = a;
   a = b;
   b = temp;
}
int linearSearch(const int arr[], int size, int value,int &count_linearSearch)
{
   int index = 0;
   int position = -1;
   bool found = false;

   while (index < size && !found)
   {
       count_linearSearch++;        //Counting number of comparisons in linear search
      if (arr[index] == value)
    {
         found = true;
         position = index;
      }
      index++;
   }
   return position;
}
int binarySearch(const int arr[], int n, int value,int &count_binarySearch)
{
   int first = 0,last = n - 1,middle,position = -1;
   bool found = false;

   while (!found && first <= last)
   {
      middle = (first + last) / 2;
      count_binarySearch++;     //Counting number of comparisons in binary search
      if (arr[middle] == value)
      {
         found = true;
         position = middle;
      }
      else if (arr[middle] > value)
         last = middle - 1;
      else
         first = middle + 1;
   }
   return position;
}

int main()
{
    int arr[120],
        i,
        value, //Element to be searched
        p;
    int count_linearSearch=0,//To count the number of comparisons of linear search
        count_bubbleSort=0,//To count the number of comparisons of bubble sort
        swap_bubbleSort=0,//To count the number of swaps of bubble sort
        count_selectionSort=0,//To count the number of comparisons of selection sort
        swap_selectionSort=0,//To count the number of swaps of selection sort
        count_binarySearch=0;//To count the number of comparisons of binary search
    for(i=0;i<120;i++)
        arr[i]=(rand() % 100) + 1;   //To generate random numbers in the range of 1 to 100 as array elements
    cout<<"The array elements  are : ";
    for(i=0;i<120;i++)
       cout<<arr[i]<<" ";  //Printing array elements
    cout<<endl;
    cout<<"Enter value : ";
    cin>>value;
    cout<<endl;

    p=linearSearch(arr, 120, value,count_linearSearch);
    cout<<"The number of comparisons in linear search are : "<<count_linearSearch<<endl<<endl;  //Printing number of comparisons in linear search

    bubbleSort(arr,120,count_bubbleSort,swap_bubbleSort);     //To sort the array before the search
    p=binarySearch(arr, 120, value,count_binarySearch);
    cout<<"The number of comparisons in binary search are : "<<count_binarySearch<<endl<<endl;  //Printing number of comparisons in binary search

    cout<<"Position of element : "<<p<<endl<<endl;  //Printing Position of element in array

    for(i=0;i<120;i++)
        arr[i]=(rand() % 100) + 1;
    cout<<"The array elements  are : ";
    for(i=0;i<120;i++)
       cout<<arr[i]<<" ";
    cout<<endl<<endl;

    bubbleSort(arr,120,count_bubbleSort,swap_bubbleSort);
    cout<<"The number of comparisons in bubble sort are : "<<count_bubbleSort<<endl;    //Printing number of comparisons in bubble sort
    cout<<"The number of swaps in bubble sort are : "<<swap_bubbleSort<<endl<<endl;     //Printing number of swaps in bubble sort

    for(i=0;i<120;i++)
        arr[i]=(rand() % 100) + 1;
    cout<<"The array elements  are : ";
    for(i=0;i<120;i++)
       cout<<arr[i]<<" ";
    cout<<endl<<endl;

    selectionSort(arr,120,count_selectionSort,swap_selectionSort);
    cout<<"The number of comparisons in selection sort are : "<<count_selectionSort<<endl;  //Printing number of comparisons in selection sort
    cout<<"The number of swaps in selection sort are : "<<swap_selectionSort<<endl;         //Printing number of swaps in selection sort

    return 0;
}

The output of the code :

PLEASE LIKE THE ANSWER IF YOU FIND IT HELPFUL OR YOU CAN COMMENT IF YOU NEED CLARITY / EXPLANATION ON ANY POINT.