Purpose: Get used to the
concept of object-oriented programming by using vector objects of the powerful
Overview:
Sample Executable: Your program should work like the demo executable here, which allows the user to (i) provide and
merge numbers in two sorted vectors into a single sorted vector and (ii)
provide and sort the numbers in a vector.
Structure of your program: You only need a single cpp file for this assignment
and the structure should looks like the following:
#include <iostream>
#include <vector>
using
namespace std;
bool
mergeTwoSortedVectors
(vector<double>
& vecA, vector<double> & vecB, vector<double> & vecC)
{
//Your code
}
void
mergeSort(vector<double> & vecToSort)
{
//Your code
}
int
main( )
{
//Your code
}
Step 1: Implement the mergeTwoSortedVectors function
Given
(references to) two vector<double> vectors vecA and vecB, each of which contains values already sorted in
ascending order, implement the following function that can merge the values
stored in these two separate sorted vector into a single vector vecC with all the values in it sorted in
ascending order.
bool
mergeTwoSortedVectors
(vector<double>
& vecA, vector<double> & vecB, vector<double> & vecC)
{
//Your code
}
Checking the
precondition:
The
values stored in vecA and those in vecB must be in ascending order already.
Your implementation should check to make sure they are already sorted, and if
they are not both sorted, stop and return false.
(The mergeTwoSortedVectors function should check this.). You should also
invoke the resize( ) member function from vecC before any merging operations to make sure vecC
is of the right size to store all the values in
vecA and vecB.
Implementation of the merge operations:
For
vector vecA, use a separate integer
variable countA to keep the count of
the number of elements in vector vecA
(starting from the beginning of the vector vecA)
already merged into the vector vecC.
Do the same thing with an integer variable countB
for vector vecB to keep the count of
the number of elements in vector vecB
(starting from the beginning of the vector vecB)
already merged into the vector vecC.
For vector vecC, keep an integer
variable countC as the count of the
number of elements already merged (from both vecA and vecB) into vecC. Initially all three counts are
simply 0.
Essentially you need to implement three
separate loops below:
Loop 1: Repeatedly do the following as long as vecA and vecB both still have elements not yet merged
into vecC:
1. Compare the next element to merge in vecA (i.e. vecA[countA]) with the
next element to merge in vecB (i.e. vecB[countB]) .
2. Pick the smaller of the two values, merge it into vecC by copying it into the vecC[countC]
in vecC.
3. Update the counts in countA, countB, and countC accordingly.
Note
that after Loop 1 is finished, the elements in one of the two vectors (vecA or vecB) must have been completely merged into vecC by this time. We
need to copy whatever the remaining elements in vecA or vecB into vecC using the following two loops.
(Note that exactly only one of Loop 2 and Loop 3 below will encounter any
remaining elements needed to be copied into vecC.)
Loop 2: Use a loop to copy all the remaining elements left in vecA into vecC one by one.
Loop 3: Use a loop to copy the remaining elements left in vecB into vecC one by one.
After Loop 3, return true.
Step 2: Test the implementation of the
mergeTwoSortedVectors function
Create
a loop in your main function to repeatedly do the following test on the mergeTwoSortedVectors
function until the user enters a
negative value for n1 or n2 in the input:
· Declare three separate vector<double> vectors. Ask the user to enter two
non-negative integers n1 and n2. Resize those three vectors to the
sizes of n1, n2, and (n1+n2)
respectively. Then use a loop to ask the user to enter a series of n1 sorted values and store them in the
vector (of size n1). Similarly use a
loop to ask the user to enter a series of n2
sorted values and store them in the vector (of size n2). Then call the mergeTwoSortedVectors function appropriately to merge the two
series of sorted values in the first two vectors into the one sorted series of
values stored in the third vector. Output the contents of the (n1+n2)
element in the third vector to verify that the two sorted series stored
in the first two vectors have been correctly merged into a sorted series stored in the third vector.
You have to make sure that mergeTwoSortedVectors
is working perfectly (by doing extensive testing in Step 2) before you
proceed to Step 3 below.
If you are 100% sure your mergeTwoSortedVectors
is working, you can comment out the testing code in the main function when
you proceed to Step 3 below.
Step 3: Implement the mergeSort function
Implement
the following recursive merge sort function by using the mergeTwoSortedSeries
function implemented in Step 1.
void
mergeSort(vector<double> & vecToSort)
{
//Your code
}
· If the size of vecToSort is 1 or less, it is already sorted just return.
· If the size
of vecToSort is 2, compare the two elements in it and swap
them if necessary, and then return.
· Otherwise, the
size of vecToSort is at
least 3. In this case, we should use two separate vectors vec1 and vec2 (as local
objects), resize them to the sizes vecToSort.size( )/2 and
vecToSort.size( ) -
vecToSort.size( )/2 respectively,
and copy the first vecToSort.size( )/2 elements in vecToSort into the first
vector and the remaining vecToSort.size(
) - vecToSort.size( )/2 into the second vector.
· Call mergeSort(vec1) to sort the first vector.
· Call mergeSort(vec2) to sort the second vector.
· Call mergeTwoSortedVectors(vec1, vec2, vecToSort) to
merge the two sorted vectors vec1 and
vec2 into vecToSort to make it a sorted vector
Step 4: Test the implementation of the
mergeSort function
Create
a loop in your main function to repeatedly do the following test on the mergeSort
function until the user enters a
negative value for n in the input:
· Declare a vector<double>
vector. Ask the user to enter one non-negative integer n. Resize the vector to the size of n. Use a loop to ask the user to enter a series of n sorted values and store them in the
vector of size n. Then call the mergeSort
function appropriately to sort the
vector. Output the contents of this final sorted series to verify the
result.
When you are sure mergeSort
is working perfectly, you are done.