In: Computer Science
Write a C++ program that implements both the recursive binary and mergesort algorithms as described in zyBooks sections 9.4 and 9.5. Prompt the user for the location of a sequence of numbers, via an external file or data entry by the user. If you choose data entry, prompt the user for the number of values and read them into a data structure of your choice. Then use the mergesort algorithm to sort them in ascending order. Finally, prompt for a value for which to use the binary search and return the location if found or indicate it was not found.
#include <iostream>
using namespace std;
void merge(int *,int, int , int );
void merge_sort(int *arr, int low, int high)
{
int mid;
if (low < high){
//divide the array at middle position
mid=(low+high)/2;
merge_sort(arr,low,mid);// recursive call
merge_sort(arr,mid+1,high);//recursive call
//merge sorted arrays
merge(arr,low,high,mid);
}
}
// Merge sort
void merge(int *arr, int low, int high, int mid)
{
int i, j, k, c[50];
i = low;// set i to low ie, start index
k = low; // set k to low
j = mid + 1;
//place values from arr to c in sorted order.
while (i <= mid && j <= high) {
if (arr[i] < arr[j]) {
c[k] = arr[i];
k++;
i++;
}
else {
c[k] = arr[j];
k++;
j++;
}
}
//if any elements are left after previous while loop, place that into c.
while (i <= mid) {
c[k] = arr[i];
k++;
i++;
}
while (j <= high) {
c[k] = arr[j];
k++;
j++;
}
//copy c into arr
for (i = low; i < k; i++) {
arr[i] = c[i];
}
}
//binary search
int binarySearch(int *arr, int l, int r, int x)
{
if (r >= l) {
int mid = (r + l) / 2;
// If element is present at the middle
if (arr[mid] == x)
return mid;
if (arr[mid] > x) {
return binarySearch(arr, l, mid - 1, x); }//recursive call
else{
return binarySearch(arr, mid + 1, r, x); }//recursive call
}
// We reach here when element is not
// present in array
return -1;
}
// read input array and call mergesort
int main()
{
int myarray[30], num;
cout<<"Enter number of elements to be sorted:";
cin>>num;
cout<<"Enter "<<num<<" elements to be sorted:";
for (int i = 0; i < num; i++) { cin>>myarray[i];
}
merge_sort(myarray, 0, num-1);
cout<<"Sorted array\n";
for (int i = 0; i < num; i++)
{
cout<<myarray[i]<<"\t";}
int x;
cout<<"\nEnter the number to be found:";
cin>>x;
int size = sizeof(myarray) / sizeof(myarray[0]);
int result = binarySearch(myarray, 0, size - 1, x);
if(result==-1){
cout << "Element is not found in array"; }
else{
cout << "Element is found at index " << result;//index position starts from 0.
}
}
Screenshots. Please note that the index position starts at 0.