In C++, Vector and Sorting Program Will rate best solution thumbs up! Two files,
ID: 3709989 • Letter: I
Question
In C++, Vector and Sorting Program
Will rate best solution thumbs up!
Two files, datal and data2, each contain one or more integers separated by whitespace. You are to do the following: 1. Read the values from datal into a vector 2. Display the vector 3. Sort the array using insertion sort 4. Display the vector 5. Read the values from data2 into the vector after the existing, now sorted, values 6. Display the vector 7. Sort the array using merge sort 8. Display the vector You will write the following functions (prototypes given): void read (ifstream &, vector &); reads all values from the file into the vector. Values should be begin being inserted at the "end" of the vector, after all other values. void display (vector &); displays all values in the vector, each separated by a single space and with an endline at the end. void insertion sort (vector &) ; sorts the array using insertion sort • void merge_sort (vector &) ; sorts the vector using mergesort (in place) O You may modify this function prototype as needed and/or use additional functions as necessary to be called from mergesort only.Explanation / Answer
#include <iostream>
#include <cstdlib>
#include <sstream>
#include <string>
#include <fstream>
#include <iomanip>
#include <vector>
using namespace std;
void read(ifstream &, vector <int> &);
void display(vector <int> &);
void insertion_sort(vector <int> &);
void merge_sort(vector <int> &);
void read(ifstream & file, vector <int> &myVector){
int number;
file >> number;
while (!(file.eof() || file.fail())) {
myVector.push_back(number);
file >> number;
}
}
void display(vector <int> &myVector){
vector <int> :: iterator i;
for (i = myVector.begin(); i != myVector.end(); ++i){
if (i+1 == myVector.end()){
cout << *i ; // dont give extra space for last element
}
else{
cout << *i << ' ';
}
}
}
void merge(vector <int> &myVector, int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* create temp arrays */
int L[n1], R[n2];
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = myVector[l + i];
for (j = 0; j < n2; j++)
R[j] = myVector[m + 1+ j];
/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
myVector[k] = L[i];
i++;
}
else
{
myVector[k] = R[j];
j++;
}
k++;
}
/* Copy the remaining elements of L[], if there
are any */
while (i < n1)
{
myVector[k] = L[i];
i++;
k++;
}
/* Copy the remaining elements of R[], if there
are any */
while (j < n2)
{
myVector[k] = R[j];
j++;
k++;
}
}
/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void merge_sort(vector <int> &myVector, int l, int r)
{
if (l < r)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l+(r-l)/2;
// Sort first and second halves
merge_sort(myVector, l, m);
merge_sort(myVector, m+1, r);
merge(myVector, l, m, r);
}
}
int main(){
vector <int> myVector;
ifstream in;
in.open("data1");
read(in, myVector);
display(myVector);
printf(" ");
in.close();
in.open("data2");
read(in, myVector);
display(myVector);
printf(" ");
in.close();
merge_sort(myVector, 0, myVector.size() - 1);
display(myVector);
printf(" ");
return 0;
}