Question

In: Computer Science

Write a C++ program that implements both the recursive binary and mergesort algorithms as described in...

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.

Solutions

Expert Solution

#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.


Related Solutions

Write a program in C language that implements the logic of Binary Trees with the following...
Write a program in C language that implements the logic of Binary Trees with the following requirements: 1- Elements of the tree should be read from the user. 2- Keep the binary tree heigh-balanced that is the absloute value of ((hight of left sub-tree) - ( height of right sub-tree)) should not be greater than 1. If so, then the binary tree is no longer balanced. Hint: The best approach is to maintain balance during insertion. *Remember, we are talking...
Write a program that implements the follow disk scheduling algorithms. You can use C or Java...
Write a program that implements the follow disk scheduling algorithms. You can use C or Java for this assignment. FCFS SSTF SCAN C-SCAN LOOK C-LOOK Your program will service a disk with 5000 cylinders (numbered 0 to 4999). Your program will generate a random initial disk head position, as well as a random series of 1000 cylinder requests, and service them using each of the 6 algorithms listed above. Your program will report the total amount of head movement required...
Write a JAVA program that implements the following disk-scheduling algorithms: FCFS
Write a JAVA program that implements the following disk-scheduling algorithms: FCFS
Task: Write a program that implements several sorting algorithms and use it to demonstrate the comparative...
Task: Write a program that implements several sorting algorithms and use it to demonstrate the comparative performance of the algorithms for a variety of datasets. Background The skeleton program sorting.cpp contains a main function for testing the operation of several sort algorithms over various data sizes and dataset organisations. The program understands the following arguments: -i insertion sort -s selection sort (default) -q quicksort -a (already) sorted dataset -v reverse-sorted dataset -r random dataset (default) -n no sorting x generate...
Write a program that implements the FIFO, LRU, and Optimal page replacement algorithms presented in chapter...
Write a program that implements the FIFO, LRU, and Optimal page replacement algorithms presented in chapter 8 of your text. First generate a random page-reference string (this should be 20 entries long) where page numbers range from 0 to 9. Apply the random page-reference string to each algorithm, and record the number of page faults incurred by each algorithm. Implement the replacement algorithms so that the number of page frames goes from 1 to 7 and you must compute the...
Write pseudocode algorithms for the programs described as follows:- Available Credits A program that calculates a...
Write pseudocode algorithms for the programs described as follows:- Available Credits A program that calculates a customer’s available credit should as the user for the following:  The customers maximum amount of credit  The amount of credit used by the customer Once these items have been entered, the program should calculate and display the customer’s available credit. You can calculate available credit by subtracting the amount of the credit used from the maximum amount of credit. (I need this...
Write an MSP430 assembly language program that implements the following 2 algorithms: 2) a macro called...
Write an MSP430 assembly language program that implements the following 2 algorithms: 2) a macro called "vdot" that calculates the "dot product" of two vectors "a" and "b", implemented as “arrays” (following the “C” language convention), of 3 elements. the macro should receive 2 pointers to the first element of each vector and return the result in R13.
IN jAVA Language PLEASE Write a JAVA program that implements the following disk-scheduling algorithms: a. FCFS...
IN jAVA Language PLEASE Write a JAVA program that implements the following disk-scheduling algorithms: a. FCFS b. SSTF c. SCAN Your program will service a disk with 5,000 cylinders numbered 0 to 4,999. The program will generate a random series of 50 requests and service them according to each of the algorithms you chose. The program will be passed the initial position of the disk head as a parameter on the command line and report the total amount of head...
Outcomes: • Write a Java program that implements linked list algorithms can u also show thee...
Outcomes: • Write a Java program that implements linked list algorithms can u also show thee testing code -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- This is the starter code import java.util.NoSuchElementException; // Put your prologue comments here public class LinkedAlgorithms {       private class Node {        private String data;        private Node next;        private Node(String data) {            this.data = data;            this.next = null;        }    }    public Node head;   ...
a) Based on the binary tree implementation from the Python program below  write a recursive method that...
a) Based on the binary tree implementation from the Python program below  write a recursive method that calculates the number of leaf nodes in the tree. class Binaertre: def __init__(self, datatobjekt): self.data = datatobjekt self.forelder = None self.venstre_barn = None self.hoyre_barn = None @property def venstre_barn(self): return self.__venstre_barn @venstre_barn.setter def venstre_barn(self, node): self.__venstre_barn = node if node is not None: node.forelder = self @property def hoyre_barn(self): return self.__hoyre_barn @hoyre_barn.setter def hoyre_barn(self, node): self.__hoyre_barn = node if node is not None: node.forelder...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT