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 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...
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 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...
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...
C++ Goals: Write a program that works with binary files. Write a program that writes and...
C++ Goals: Write a program that works with binary files. Write a program that writes and reads arrays to and from binary files. Gain further experience with functions. Array/File Functions Write a function named arrayToFile. The function should accept three arguments: the name of file, a pointer to an int array, and the size of the array. The function should open the specified file in binary made, write the contents into the array, and then close the file. write another...
please write a C program that implements Quick Sort algorithm.
please write a C program that implements Quick Sort algorithm.
Write a C++ program to compare those two searching algorithms and also compare two sorting algorithms....
Write a C++ program to compare those two searching algorithms and also compare two sorting algorithms. You need to modify those codes in the book/slides to have some counters to count the number of comparisons and number of swaps. In the main function, you should have an ordered array of 120integers in order to test searching algorithms, and the other two identical arrays of 120integers not in order to test sorting algorithms. Display all counters in the main functions.Counter for...
Objective: Write a C++ -program that will implement 4 Memory Management algorithms Algorithms: A) Best-Fit B)...
Objective: Write a C++ -program that will implement 4 Memory Management algorithms Algorithms: A) Best-Fit B) First-Fit C) Next-Fit D) Worst-Fit Your program must do the following: 1. Program Input:             User will input to the program a. Main Memory information, including i. The Number of Memory partitions. ii. The Size of each memory partition. b. Process information (assign a unique identifier to each job) i. User will input the number of processes ii. Memory requirements for each process/job 2....
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT