Question

develop the Binary search with swap count: Use sorted data from insertion sort (part A) Permutations, Insertion Sort – implement algorithms Permutations (Johnson Trotter): {1, 2, 3, 4, 5}; Insertion Sort: {45, 24, 16, 92, 71, 69, 28} develop count of # data “insertions” and develop # of key compares against the following: 16, 77, 24, 92, 44

Answer 1

//C++ program

#include<iostream>
using namespace std;

void insertionSort(int a[],int n){
   for(int i=1;i<n;i++){
       int j=i-1,val=a[i];
       while(j>=0&&a[j]>val){
       a[j+1]=a[j];
       j--;}
       a[++j]=val;
   }
}

int binarySearch(int arr[], int l, int r, int key,int &count)
{
if (r >= l) { count++;
int mid = l + (r - l) / 2;
if (arr[mid] == key)
return mid;

if (arr[mid] > key)
return binarySearch(arr, l, mid - 1, key,count);
  
return binarySearch(arr, mid + 1, r, key,count);
}

return -1;
}

int main(){
   int arr[] = {45, 24, 16, 92, 71, 69, 28};
   int n = sizeof(arr)/sizeof(arr[0]);
   insertionSort(arr,n);
   int count;
  
   int keys[] = {16, 77, 24, 92, 44};
  
   for(int i=0;i<5;i++){
       count=0;
       int index = binarySearch(arr,0,n-1,keys[i],count);
      
       if(index!=-1){
           cout<<arr[i]<<" found at index : "<<index<<"\n";
       }
       else cout<<arr[i]<<" not found \n";
      
       cout<<"Total comparision count : "<<count<<"\n\n";
   }
   return 0;
}

//sample output