Description
Programming Part:
1. Rewrite the recursive part of the merge sort algorithm presented in class to work with any container which
You will not write your own merge method. Instead you will use the STL merge algorithm.tmp( sz );mergeSort( tmp.begin(), start, end );}The STL algorithm merge takes five arguments, first1, last1, first2, last2, result. The mergealgorithm combines “the elements in the sorted ranges [first1,last1) and [first2,last2), into a new rangebeginning at result with all its elements sorted.”12. Create a functor called meFirst which has a private member variable, me, of type string. Its constructorwill take one argument of type string that it uses to initialize its private private member variable, me.The functor’s overloaded operator() takes two arguments of type student and returns a boolean value.It returns true if the first students’ name is less than the second students’ name unless either of thestudents’ name equals the variable me then that name is always less than the other name.Test your functor using the STL 3 parameter algorithm sort, the student class we discussed in class andsome data you create yourself.2∗10% extra credit will be given if you turn this assignment in on Wednesday March 91The quote is from http://www.cplusplus.com/reference/algorithm/merge/. Don’t forget to copy the elements back into theoriginal container after calling the merge function. The STL merge function does NOT have the same signature as the mergefunction we discussed in class. You might need to include #include< algorithm >2This is a biased sort. One item is always first regardless of the other items.13. 3 Write an algorithm to do the following: given a vector of boolean values (true/false), order thecontainer such that the false values come before the true values. Your algorithm must run in O(n) anduse O(1) space.You algorithm may not simply count the number of true or false values and then assign the correctnumber of false and true values in the vector. You should think of your algorithm as the first step increating an algorithm that sorts based on true/false values, where the items are not simply true/falsevalues, but large objects that evaluate to true/false by using a functor.Hint: Be inspired by one of the sorting algorithms we discussed in class.4. (Extra Credit)4 Rather than sorting the numbers in either ascending or descending order, suppose wewanted to sort the an array in a new way. The criteria for this sort is given as: if the index of the i’thelement is odd, then that element should be less than it’s neighboring elements. If the index of the i’thelement is even, it should be greater than it’s neighboring elements. Your algorithm must run in O(n log n)time and can use at most O(n) extra spaceEx: Consider the array [5, 9, 8, 2, 3, 4]. After the sort the array should have: [5, 2, 4, 3, 9, 8]Explanation: 5 is at index 0, so it must be greater than it’s neighbors ( 2 )2 is at index 1, so it must be less than it’s neighbors (5 & 4)4 is at index 2, so it must be greater than it’s neighbors (2 & 3)…. and so onNote: The solution may not be unique.3This problem is from Shahzaib, our TA!4This problem is from Shahzaib, our TA!2Written Part:1. The C++ STL has many functions and functors. Here is your chance to try some of them. In a program when you use an STL algorithm add #include, and when you use an STL functor add#include. Fill in the correct code where you see a ****vector A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};vector B = {1, 2, 1, 2, 1, 2};vector C(16);(a) Sort the first 4 items in vector Bsort(B.begin( ), ****); // B now contains 1, 1, 2, 2, 1, 2(b) Sort the the vector A in reverse order using the functor greatersort(A.begin( ), ****, ****); //A now contains 10, 9, 8, 7, 6, 5, 4, 3, 2, 1(c) Sort the items in vector B in reverse ordersort(B.begin( ), ****, ****);// B now contains 2, 2, 2, 1, 1, 1(d) Merge A and B into C. Note that C must have enough space to store both A and B. Since both A andB are sorted in reverse order, you need to pass in a functor to compare the items in the containersmerge(A.begin( ), ****, B.begin( ), ****, C.begin( ), greater());// C now contains 10, 9, 8, 7, 6, 5, 4, 3, 2, 2, 2, 2, 1, 1, 1, 12. Is our mergeSort algorithm stable5?3. What would be printed out by the following code, if the vector a contained {11, 10, 1, 3, 2, 5}, and thefunction printVec printed out contents of a? (Don’t worry about the exact format of the output, thepoint is to show how the contents of the vector is or is not changing)templatevoid insertionSort( vector & a ){int j;for( int p = 1; p < a.size( ); p++ ) { Comparable tmp = a[ p ]; for( j = p; j > 0 && tmp < a[ j – 1 ]; j– )a[ j ] = a[ j – 1 ];a[ j ] = tmp;printVec(a); // prints the contents of the vector in order}}5“Stable sorting algorithms maintain the relative order of records with equal keys (i.e. values). That is, a sorting algorithm isstable if whenever there are two records R and S with the same key and with R appearing before S in the original list, R will appearbefore S in the sorted list.” from https://en.wikipedia.org/wiki/Category:Stable sorts34. What would be printed out by the following code, if the vector a contained {11, 10, 1, 3, 2, 5}, and thefunction printVec printed out contents of a? (Don’t worry about the exact format of the output, thepoint is to show how the contents of the vector is or is not changing)template void mergeSort( vector & a, vector & tmpArray, int left, int right ){if( left < right ){int center = ( left + right ) / 2;mergeSort( a, tmpArray, left, center );mergeSort( a, tmpArray, center + 1, right );mymerge( a, tmpArray, left, center + 1, right );printVec(a); // prints the contents of the vector in order}}5. What would be printed out by the following code, if the vector a contained {11, 10, 1, 3, 2, 5}, and thefunction printVec printed out contents of a? (Don’t worry about the exact format of the output, thepoint is to show how the contents of the vector is or is not changing)void quickSort( vector & a, int low, int high ){if (low < high){int mid = ( low + high )/2; // select pivot to be element in middle positionint pivot = a[ mid ];swap( a[high], a[mid] ); // put pivot in a[high]// Begin partitioningint i, j;for( i = low, j = high – 1; ; ){while ( a[i ] < pivot ) ++i; while( j > i && pivot < a[j ] ) –j;if( i < j )swap( a[ i++ ], a[ j– ] );elsebreak;}swap( a[ i ], a[ high ] ); // Restore pivotprintVec(a); // prints the contents of the vector in orderquickSort( a, low, i – 1 ); // Sort small elementsquickSort( a, i + 1, high ); // Sort large elements}}46. Show all the function calls organized as a recursion tree where you include the contents of the containera for:(a) mergeSort on input a = {28, 10, 2, 27, 5, 1}(b) quickSort on input a = {28, 10, 2, 27, 5, 1}7. When all the items in the vector are in ”almost” sorted order (e.g. a contains {2, 1, 4, 3, 6, 5, . . . , n/2, n/2−1, . . . , n, n − 1}, what is the average running time in Big-Oh notation for:(a) insertionSort(b) quickSort8. For the quickSelect algorithm we discussed in class, if after the partition it turns out that i + 1 = k whydoes the function not recursively call itself?9. For the following function:(a) what is printed by the following function call: myRecFunc1(4)(b) what is the running time of myRecFunc1(n)void myRecFunc1(int n){if (n < 1) return;cout << n << “, “;myRecFunc1(n/2);cout << n << “, “;}10. For the following function:(a) what is printed by the following function call: myRecFunc2(4)(b) what is the running time of myRecFunc2(n)void myRecFunc2(int n){if (n < 1) return;cout << n << “, “;myRecFunc2(n/2);cout << n << “, “;myRecFunc2(n/2);}5
