Write a program create a vector with random numbers. Use merge sort to reorder t
ID: 3671513 • Letter: W
Question
Write a program create a vector with random numbers. Use merge sort to reorder the vector.
Prompt user to enter a number to search in the vector. If there are more than one number in the
vector equal to the search value, display the indices remove the repeated numbers. If found just
one matching number, display the index. If no matching number, prompt user for 2 options: add
to the vector or replace a value in the vector.
Writing in programming language : C++.
Sample output / example of program:
Printing original vector:
3 4 7 6 4 7 6 7 4 7
Sorting using merge sort and print vector:
3 4 4 4 6 6 7 7 7 7
Enter a number to search in the vector (1
to quit): 4
Number 4 found in the following indices:
1 2 3
Removing repeated elements of number 4
3 4 6 6 7 7 7 7
Enter a number to search in the vector (1
to quit): 7
Number 7 found in the following indices:
4 5 6 7
Removing repeated elements of number 7
3 4 6 6 7
Enter a number to search in the vector (1
to quit): 4
Number 4 found at index 1
Enter a number to search in the vector (1
to quit): 5
Number 5 not found in the vector.
Select the following options:
1. Add number to vector.
2. Replace number in vector.
Input = 1
Vector after adding number 5
3 4 5 6 6 7
Enter a number to search in the vector (1
to quit): 8
Number 8 not found in the vector.
Select the following options:
1. Add number to vector.
2. Replace number in vector.
2
Enter the number in the vector to be replaced: 7
Vector after replacing and sorting:
3 4 5 6 6 8
Enter a number to search in the vector (1
to quit):
Display the vector at every change. Do not use any global variable. Pass the vector and
variables to the function appropriately.
Explanation / Answer
Program:
// include the required header files
#include<iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;
// method protocol declaration
vector<int> mrgsort(vector<int>& valvec);
vector<int> srtmerge(const vector<int>& vecleft, const vector<int>& vecright);
// main method
int main()
{
vector<int> myVector,sortvector;
int srval, inpopt,vecrpl;
bool flg=false;
srand((unsigned)time(NULL));
for (int i =0; i<10; i++)
{
int b = rand() % 10 + 1;
myVector.push_back(b);
}
// code to print original vector values
cout<<" Printing original vector: ";
for (vector<int>::iterator it=myVector.begin(); it!=myVector.end(); ++it)
cout << ' ' << *it;
// code to sort the vector values
cout<<" Sorting using merge sort and print vector: ";
sortvector=mrgsort(myVector);
for (vector<int>::iterator it1=sortvector.begin(); it1!=sortvector.end(); ++it1)
cout << ' ' << *it1;
do
{
// code to search a value in vector
cout<<" Enter a number to search in the vector (1to quit): ";
cin>>srval;
for (int in=0;in<10;in++)
if( sortvector.at(in)==srval)
{
cout<<in<<" ";
flg=true;
}
if(flg==true)
{
// code to remove a repeated value in vector
cout<<" Removing repeated elements of number"<<srval<<endl;
int cnt=0;
for(int in2=0;in2<10;in2++)
{
if( sortvector.at(in2)==srval)
{
if(cnt>0)
sortvector.erase(sortvector.begin() + in2);
cnt++;
}
}
}
sortvector=mrgsort(sortvector);
for (vector<int>::iterator it5=sortvector.begin(); it5!=sortvector.end(); ++it5)
cout << ' ' << *it5;
// Code to add or replace the elements in a vector
if(flg==false)
{
cout<<" Number "<<srval<<" not found in the vector. ";
cout<<" Select the following options: 1. Add number to vector. 2. Replace number in vector. ";
cout<<"input=";
cin>>inpopt;
if(inpopt==1)
{
sortvector.push_back(srval);
sortvector=mrgsort(sortvector);
cout<<" Vector after adding number "<<srval<<endl;
for (vector<int>::iterator it2=sortvector.begin(); it2!=sortvector.end(); ++it2)
cout << ' ' << *it2;
}
else if(inpopt==2)
{
cout<<" Enter the number in the vector to be replaced: ";
cin>>vecrpl;
for (int in=0;in<10;in++)
if( sortvector.at(in)==vecrpl)
{
sortvector.at(in)=srval;
}
cout<<" Vector after replacing and sorting "<<srval<<endl;
sortvector=mrgsort(sortvector);
for (vector<int>::iterator it2=sortvector.begin(); it2!=sortvector.end(); ++it2)
cout << ' ' << *it2;
}
}
}while(srval!=1);
system("pause");
}
// method for merge sort
vector<int> mrgsort(vector<int>& valvec)
{
if(valvec.size() == 1)
{
return valvec;
}
std::vector<int>::iterator mid = valvec.begin() + (valvec.size() / 2);
vector<int> vecleft(valvec.begin(), mid);
vector<int> vecright(mid, valvec.end());
vecleft = mrgsort(vecleft);
vecright = mrgsort(vecright);
return srtmerge(vecleft, vecright);
}
// method to merge the values
vector<int> srtmerge(const vector<int>& vecleft, const vector<int>& vecright)
{
vector<int> vecres;
unsigned left_itra = 0, right_itra = 0;
while(left_itra < vecleft.size() && right_itra < vecright.size())
{
if(vecleft[left_itra] < vecright[right_itra])
{
vecres.push_back(vecleft[left_itra]);
left_itra++;
}
else
{
vecres.push_back(vecright[right_itra]);
right_itra++;
}
}
while(left_itra < vecleft.size())
{
vecres.push_back(vecleft[left_itra]);
left_itra++;
}
while(right_itra < vecright.size())
{
vecres.push_back(vecright[right_itra]);
right_itra++;
}
return vecres;
}
Result:
Printing original vector:
3 3 2 7 5 4 10 10 7 3
Sorting using merge sort and print vector:
2 3 3 3 4 5 7 7 10 10
Enter a number to search in the vector (1to quit):
3
1 2 3
Removing repeated elements of number3
2 3 4 5 7 7 10 10
Enter a number to search in the vector (1to quit):
7
5 6
Removing repeated elements of number7
2 3 4 5 7 10 10
Enter a number to search in the vector (1to quit):1
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.