able to keep track // frequency of copy operation (marked below), an
C++
#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)
/* 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
// 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
