Write a program that a.Calls a method called insertionSort that accepts an integ

Question

Write a program that

a.Calls a method called insertionSort that accepts an integer array as a parameterand sorts the elements in the array using the insertion sort algorithm. Print thearray before it is sorted and after it is sorted.

b.Calls another method called binarySearch that takes two parameters, an integerand an integer array. The call should perform binary search and should return theindex of the integer in the array if found and should return -(insertionPoint+ 1) ifthe number is not found. Print out the index in the main method.

Explanation / Answer

/*** c++ code to implement insertionsort and binaryserch ********/

#include <cstdlib>
#include <iostream>
#include <math.h>
#include <stdio.h>

using namespace std;

/* Function to sort an array using insertion sort*/
void insertionSort(int arr[], int size)
{
int i, key, j;

for (i = 1; i < size; i++)
{
key = arr[i];
j = i-1;

/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
}
}

void printArray(int arr[], int n)
{
int i;
for (i=0; i < n; i++)
printf("%d ", arr[i]);
printf(" ");
}

int binarySearch(int arr[], int x, int size)
{
   int l = 0;
   int r = size -1;

while (l <= r)
{
// find index of middle element
int m = (l+r)/2;

// 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 -(l+1);
}

int main()
{
   int size;
   cout << "Enter size of array: ";
   cin >> size;

   int arr[size];
   cout<<"Enter elements of array: ";
   for (int i = 0; i < size; ++i)
   {
       cin >> arr[i];
   }

   
    cout << " Given Array: "<<endl;
    printArray(arr, size);
insertionSort(arr,size);
cout << " Sorted Array: "<<endl;
printArray(arr, size);

int key;
cout <<"Enter element you want to search: ";
cin >> key;
cout << binarySearch(arr,key,size)<<endl;

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.