Finish the code algorthims #include #include using namespace std; //Todo4: Add cout statement to MergeSort () to print out // a line for each time this function is called, show the parameter // a line for each time we return from this function, show the parameter //Todo3: add a global variable to keep track // frequency of copy operation (marked below), and comparison operation (marked below) // /* Merge two sorted vectors' elements into one sorted vector @param l1, l2: two sorted vectors @param list: the vector to hold the merging result @pre-condcition: elements in l1, l2 are in ascending order @post-condcition: list contains elements from l1 and l2, in ascending order */ void BinaryMergeSortedList (const vector l1, const vector l2, vector & list) { //Idea: as well as l1 and l2 both have elements left to be copied to list, // compare the "front runner", and copy the smaller one to next slot in list. // When only one of l1, l2 have elements left, copy all remaining elements to list // one by one. //make sure list has exact same # of elements as l1, l2 combined: // (by dropping extra or adding 0 to the end) // subsequently, we can use list[k] or list.at(k) to refer to each element... // more efficient than: // 1) first: list.clear(); //make list an empty list // 2) and then: list.push_back(l1[i++]); //to add a new element into // the back (end of list). list.resize(l1.size()+l2.size()); int i,j,k; //used to index l1, l2 and list respectively i=j=k=0; //start from first position while (i
Finish the code algorthims
#include <iostream>
#include <vector>
using namespace std;
//Todo4: Add cout statement to MergeSort () to print out
// a line for each time this function is called, show the parameter
// a line for each time we return from this function, show the parameter
//Todo3: add a global variable to keep track
// frequency of copy operation (marked below), and comparison operation (marked below)
//
/* Merge two sorted
@param l1, l2: two sorted vectors
@param list: the vector to hold the merging result
@pre-condcition: elements in l1, l2 are in ascending order
@post-condcition: list contains elements from l1 and l2, in ascending order */
void BinaryMergeSortedList (const vector<int> l1, const vector<int> l2, vector<int> & list)
{
//Idea: as well as l1 and l2 both have elements left to be copied to list,
// compare the "front runner", and copy the smaller one to next slot in list.
// When only one of l1, l2 have elements left, copy all remaining elements to list
// one by one.
//make sure list has exact same # of elements as l1, l2 combined:
// (by dropping extra or adding 0 to the end)
// subsequently, we can use list[k] or list.at(k) to refer to each element...
// more efficient than:
// 1) first: list.clear(); //make list an empty list
// 2) and then: list.push_back(l1[i++]); //to add a new element into
// the back (end of list).
list.resize(l1.size()+l2.size());
int i,j,k; //used to index l1, l2 and list respectively
i=j=k=0; //start from first position
while (i<l1.size() && j < l2.size()){
if (l1[i] <= l2[j]) //comparison operation
//copy smaller one to list, and advance indices
list[k++] = l1[i++]; //copy operation
else
list[k++] = l2[j++]; //copy operation
}
//copy remaining elements to list
while (i<l1.size()) //if l1 is not done yet
list[k++] = l1[i++]; //copy operation
while (j<l2.size()) //if l2 is not done yet
list[k++] = l2[j++]; //copy operation
}
/* sort the vector into ascending order
@param list: the vector of int to be sorted
@pre-condiction: list has been initialized with some data
@post-condition: the integers stored in list are rearranged into
ascending order */
void MergeSort (vector<int> & list)
{
if (list.size()==1)
return;
//general case: divide and conquer
//divide part
int n=list.size();
int mid = (0+n-1)/2; //averge of first and last index
vector<int> leftHalf(list.begin(),list.begin()+mid+1);
// range constructor: initilize with elements from a range of existing vector:
// from first iterator (including) to last iterator (not included)
//https://www.cplusplus.com/reference/vector/vector/vector/
vector<int> rightHalf(list.begin()+mid+1,list.end());
//conquer part: solve the two subproblems recursively (and independently from
// each other
MergeSort (leftHalf);
MergeSort (rightHalf);
//Combine part: merge data from the two sorted halves
// back into list, in ascending order
BinaryMergeSortedList (leftHalf, rightHalf, list);
}
//Todo 3: split list into n vectors of size 1
// add them into a queue of vectors
// enter a loop to take two vectors from the queue, do a binaryMergeSortedList,
// push the resulting vector back into the queue
// ...
void MergeSortIterative(vector<int> & list)
{
//Todo:
}
int main()
{
vector<int> a{6,4,3,8,2,5,1,7};
MergeSort (a);
cout<<"result:";
//use iterator to go through vector a
//for (vector<int>::iterator it=a.begin(); it<a.end(); it++)
//cout <<*it <<" ";
for (auto element:a) //supported in C++11, element's type is auto
cout <<element<<" ";
cout <<endl;
//Todo 1:
// Measuring running time of MergeSort for n=10,20,50,100,500,...
// and frequency of comparison & copy operation
}
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
