Programming #3: Using the C++ STL Vector Class to Implement Merge Sort

 

Purpose: Get used to the concept of object-oriented programming by using vector objects of the powerful STL vector class and calling vector member functions to implement the merge-sort algorithm.

 

Overview: STL vectors can grow and shrink dynamically and the member functions of the STL vector class can help us more conveniently handle the dynamic nature of memory allocation. A STL vector also maintains the information of its size (the number of elements currently in it) dynamically and so we donít need separate variables or parameters to record the sizes of vectors. You can just call the size( ) member function from a vector to know the current size of the vector.

 

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 invecA 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 thevecC[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 asorted 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( )/2and 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( )/2into 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 mergethe 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.