Question

PLEASE COMPLETE BOTH PARTS (LANGUAGE: C++ if necessary)

Part I

For the following example, determine the number of comparisons that will take place during a search using both searching algorithms (Linear search and binary search). Also, list each comparison for each algorithm(Linear and binary). The number being searched for is 13.

List = {1,3,5,9,10,11,15,17,19,23,24,25,29,31,33,37,38,39,43,45,47,51,52,53,57,59,61}

Part 2

For the following example, determine the number of swaps that will take place during a sort using both sorting algorithms (bubble and selection sort). Also, list each swap for each algorithm (bubble and selection)

List = {23, 10, 3, -5, 2, 7, 0, 20, 15, 17, 9, 11, 4, 1}

Answer 1

#include <iostream>

using namespace std;

int c=0;
int s=0;

void swap(int *xp, int *yp)
{
    cout<<"Swapped "<<*xp<<" and "<<*yp<<"\n";
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

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

    for (i = 0; i < n-1; i++)
    {
        min_idx = i;
        for (j = i+1; j < n; j++)
        if (arr[j] < arr[min_idx])
            min_idx = j;

        swap(&arr[min_idx], &arr[i]);
        s=s+1;
    }
}


void bubbleSort(int arr[],int n)//bubble sort to sort both vector on the basis of scores
{
    s=0;
    bool swapp = true;
    int temp;
    while(swapp)
    {
        swapp = false;
        for (int i = 0; i < n-1; i++)
            {
            if (arr[i]>arr[i+1])
                {
                    cout<<"Swapped "<<arr[i]<<" and "<<arr[i+1]<<"\n";
                    s=s+1;
                    temp=arr[i];
                    arr[i]=arr[i+1];
                    arr[i+1]=temp;
                    swapp = true;
                }
            }
    }
}

bool binary_search(int arr[], int key,int n)//function for searching names in name vector
{
    c=0;
   int mid, left = 0 ;
   int right = n;
   while (left < right) {
      mid = left + (right - left)/2;

      if (key > arr[mid])
        {
            c=c+1;
            cout<<"Compared "<<key<<" and "<<arr[mid]<<"\n";
            left = mid+1;
        }
      else if (key < arr[mid])
      {
          c=c+1;
          cout<<"Compared "<<key<<" and "<<arr[mid]<<"\n";
            right = mid;
      }
      else
      {

            return true;
      }
   }

   return false;
}
bool linear_search(int arr[], int key,int n)
{
    c=0;
    for (int i=0;i<n;i++)
    {
        c=i+1;
        cout<<"Compared "<<key<<" and "<<arr[i]<<"\n";
        if (arr[i]==key)
        {
            return true;
        }
    }
}

int main()
{

  // int arr[] = {1,3,5,9,10,11,15,17,19,23,24,25,29,31,33,37,38,39,43,45,47,51,52,53,57,59,61};

    int arr1[] = {23, 10, 3, -5, 2, 7, 0, 20, 15, 17, 9, 11, 4, 1};
        int n = sizeof(arr1)/sizeof(arr1[0]);
        selectionSort(arr1,n);
        cout << "Selection sort swaps: "<<s<<"\n";
        cout<<"__________________________________________________\n";

    int arr2[] = {23, 10, 3, -5, 2, 7, 0, 20, 15, 17, 9, 11, 4, 1};
    n = sizeof(arr2)/sizeof(arr2[0]);
        bubbleSort(arr2,n);
        cout << "bubble sort swaps: "<<s<<"\n";
        cout<<"__________________________________________________\n";

        //////////////////////////////////////////////////////////////
        int arr3[]={1,3,5,9,10,11,15,17,19,23,24,25,29,31,33,37,38,39,43,45,47,51,52,53,57,59,61};
    n = sizeof(arr3)/sizeof(arr3[0]);
    linear_search(arr3,13,n);
    cout << "Linear search comparisons: "<<c<<"\n";
        cout<<"__________________________________________________\n";

    binary_search(arr3,13,n);
    cout << "binary search comparisons: "<<c<<"\n";
        cout<<"__________________________________________________\n";
    return 0;

}

IF YOU HAVE ANY DOUBT THEN JUST LEAVE A COMMENT AND I WILL CONNECT WITH YOU AS SOON AS POSSIBLE