cpp/cs104/sorting/merge Source

Viewing cpp/cs104/sorting/merge by redekopp@usc.edu. You have unsaved changes. Log in above to create, edit, preview and publish Websheets.

Property Value

Description
html markup
shown to student

Write a function to merge two sorted ranges of a vector. Assum the values in teh input vector between [s1,e1) and [s2,e2) are non-overlapping, sorted sequences of integers. Create a new vector 'retval' that has the merged, sorted values from those two ranges.

For example, if input is { 2, 5, 3, 4 } and s1=0,e1=2, s2=2,e2=4 should yield a merged result of { 2, 3, 4, 5}

Epilogue
html markup
shown when solved

remove
Public permissions remove
Remarks
Comments, history, license, etc.

Originally by Mark Redekopp (redekopp@usc.edu) and Dave Pritchard (daveagp@gmail.com)

remove
Engine
Choices
json list of string, bool pairs
e.g. [["good", true], ["bad", false]]

Correct answer
Template / Reference solution

Template / Reference solution

#include <vector>
#include <iostream>
using namespace std;

vector<int> merge(vector<int>& input,
int s1, int e1, int s2, int e2)
{
vector<int> result;
\[
while(s1 < e1 && s2 < e2){
if(input[s1] < input[s2]){
result.push_back(input[s1++]);
}
else {
result.push_back(input[s2++]);
}
}
while(s1 < e1){
result.push_back(input[s1++]);
}
while(s2 < e2){
result.push_back(input[s2++]);
}
]\
return result;
}

void print_vec(vector<int> input){
for(vector<int>::iterator it = input.begin();
it != input.end();
++it){
cout << *it << " ";
}
cout << endl;
}
int main()
{
int d1[] = {2,9,10,16,3,4,5,6};
vector<int> v1(d1, d1+8);
print_vec( merge(v1,0,4,4,8) );

int d2[] = {1,2,3,4,7,8,5,6};
vector<int> v2(d2, d2+8);
print_vec( merge(v2,4,6,6,8) );

vector<int> v3;
print_vec( merge(v3,0,0,0,0) );

return 0;

}

Java test suite
See manual

C++ test suite
json list of stdin/args tests
e.g. [{"stdin":"hi", "args":["4", "5"]}, {"stdin":"noargs"}]
to just run once with no input use [{}]

[
{}
]

C++ test suite
See manual

Forbidden substrings
json list of strings
e.g. ["for","while"]

remove
Solution visibility remove
Java imports
json list of importables
e.g. ["java.util.*"]

remove
Override Java classname
else defaults to
websheet name
remove
Dependent on other websheets?
json list of websheet names in this folder
e.g. ["DataStructure"]

remove
Is example?
i.e., just a demo
remove
Add compiler flag(s)
json list of flags
e.g. ["-Wno-unused-variable"]

remove
Remove default compiler flag(s)
json list of flags
see default_cppflags
e.g. ["-Wno-write-strings"]

remove

Property	Value
Description html markup shown to student	Write a function to merge two sorted ranges of a vector. Assum the values in teh input vector between [s1,e1) and [s2,e2) are non-overlapping, sorted sequences of integers. Create a new vector 'retval' that has the merged, sorted values from those two ranges. For example, if input is { 2, 5, 3, 4 } and s1=0,e1=2, s2=2,e2=4 should yield a merged result of { 2, 3, 4, 5}
Epilogue html markup shown when solved	remove
Public permissions	remove
Remarks Comments, history, license, etc.	Originally by Mark Redekopp (redekopp@usc.edu) and Dave Pritchard (daveagp@gmail.com) remove
Engine
Choices json list of string, bool pairs e.g. `[["good", true], ["bad", false]]`
Correct answer
Template / Reference solution
Template / Reference solution	#include <vector> #include <iostream> using namespace std; vector<int> merge(vector<int>& input, int s1, int e1, int s2, int e2) { vector<int> result; \[ while(s1 < e1 && s2 < e2){ if(input[s1] < input[s2]){ result.push_back(input[s1++]); } else { result.push_back(input[s2++]); } } while(s1 < e1){ result.push_back(input[s1++]); } while(s2 < e2){ result.push_back(input[s2++]); } ]\ return result; } void print_vec(vector<int> input){ for(vector<int>::iterator it = input.begin(); it != input.end(); ++it){ cout << *it << " "; } cout << endl; } int main() { int d1[] = {2,9,10,16,3,4,5,6}; vector<int> v1(d1, d1+8); print_vec( merge(v1,0,4,4,8) ); int d2[] = {1,2,3,4,7,8,5,6}; vector<int> v2(d2, d2+8); print_vec( merge(v2,4,6,6,8) ); vector<int> v3; print_vec( merge(v3,0,0,0,0) ); return 0; }
Java test suite See manual
C++ test suite json list of stdin/args tests e.g. `[{"stdin":"hi", "args":["4", "5"]}, {"stdin":"noargs"}]` to just run once with no input use `[{}]`	[ {} ]
C++ test suite See manual
Forbidden substrings json list of strings e.g. `["for","while"]`	remove
Solution visibility	remove
Java imports json list of importables e.g. `["java.util.*"]`	remove
Override Java classname else defaults to websheet name	remove
Dependent on other websheets? json list of websheet names in this folder e.g. `["DataStructure"]`	remove
Is example? i.e., just a demo	remove
Add compiler flag(s) json list of flags e.g. `["-Wno-unused-variable"]`	remove
Remove default compiler flag(s) json list of flags see default_cppflags e.g. `["-Wno-write-strings"]`	remove

Optional properties:

Note: problems are open-source by default (see 'Public permissions'). Assumed license for open problems is Creative Commons 4.0 Attribution-ShareAlike unless specified in 'Remarks'.