cpp/datastruct/qmerge Source

Viewing cpp/datastruct/qmerge by daveagp@gmail.com. You have unsaved changes. Log in above to create, edit, preview and publish Websheets.

Property Value

Description
html markup
shown to student

Write code to sort a list of integers using merge sort. You will use the <tt>deque<int></tt> template type.
<ol>
<li>
Create a function <tt>deque<int> merge(deque<int> a, deque<int> b)</tt> which, assuming
<tt>a</tt> and <tt>b</tt> are both deques sorted in increasing order, returns a new deque
consisting of all their elements combined, sorted in increasing order. E.g., if <tt>a</tt> is a deque into which
1 and 9 have been inserted, and <tt>b</tt> is a deque into which 2 and 6 have been inserted, then the returned
deque should contain 1 first, then 2, 6, 9.
</li>
<li>
Then, create a function <tt>deque<int> merge_sort(deque<int> input)</tt> to implement merge sort.
It should use <tt>size()</tt> from the <tt>deque</tt> API to break the deque into two
(non-ordered) deques each about half as big as the original. Then sort both halves recursively, and merge them.
</li>
</ol>
You will also need to use
<tt>bool deque::empty()</tt> as well as <tt>push_back()</tt>, <tt>front()</tt> and <tt>pop_front()</tt>.

Epilogue
html markup
shown when solved

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

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

Correct answer
Template / Reference solution

Template / Reference solution

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

// ASSUMING a and b are sorted in increasing order, return a new queue
// consisting of the elements of both in combined increasing order
deque<int> merge(deque<int> a, deque<int> b) {
deque<int> result;

// keep going as long as there are elements to merge in BOTH
while (\[!a.empty() && !b.empty()]\) {
// take the smaller element from either a or b, move it to result
\[
if (b.front() < a.front()) {
result.push_back(b.front());
b.pop_front();
}
else {
result.push_back(a.front());
a.pop_front();
}
]\
}

// if anything is left over once one queue is empty, move it into result
\[
while (!a.empty()) {
result.push_back(a.front());
a.pop_front();
}
while (!b.empty()) {
result.push_back(b.front());
b.pop_front();
}
]\
return result;
}

// return a new queue consisting of the same elements in sorted order
deque<int> merge_sort(deque<int> input) {
if (input.size() == 1) { // base case
\[
return input;
]\
}
else {
// move half the elements into a new queue
\[
int halfSize = input.size() / 2;
deque<int> firstHalf;
for (int i=0; i<halfSize; i++) {
firstHalf.push_back(input.front());
input.pop_front();
}
]\
// sort both halves and merge
return \[merge(merge_sort(firstHalf), merge_sort(input))]\;
}
}

// read all integers from input, sort them, and print them
int main(int argc, char* argv[]) {
deque<int> data;
int value;
while (cin >> value)
data.push_back(value);
deque<int> sortedData = merge_sort(data);
while (!sortedData.empty()) {
cout << sortedData.front() << " ";
sortedData.pop_front();
}
}

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 [{}]

[
{"stdin": "9 1 6 2"},
{"stdin": "3 7 8 2 4 5 2 4 1"},
{"stdin": "29 48 72 90 53 31 81 8 12 71 9 42 46 76 36 59 75 7 18 74 67 40 98 30 63 11 24 91 64 6 75 26 95 26 79 43 2 65 21 9 28 46 29 8 23 72 78 28 12 51 32 70 80 25 95 27 26 41 62 80 6 1 60 97 83 64 30 33 42 33 41 46 9 24 96 12 71 56 11 42 25 22 53 92 83 62 44 43 63 58 16 28 69 20 20 70 65 53 93 33"}
]

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 code to sort a list of integers using merge sort. You will use the <tt>deque<int></tt> template type. <ol> <li> Create a function <tt>deque<int> merge(deque<int> a, deque<int> b)</tt> which, assuming <tt>a</tt> and <tt>b</tt> are both deques sorted in increasing order, returns a new deque consisting of all their elements combined, sorted in increasing order. E.g., if <tt>a</tt> is a deque into which 1 and 9 have been inserted, and <tt>b</tt> is a deque into which 2 and 6 have been inserted, then the returned deque should contain 1 first, then 2, 6, 9. </li> <li> Then, create a function <tt>deque<int> merge_sort(deque<int> input)</tt> to implement merge sort. It should use <tt>size()</tt> from the <tt>deque</tt> API to break the deque into two (non-ordered) deques each about half as big as the original. Then sort both halves recursively, and merge them. </li> </ol> You will also need to use <tt>bool deque::empty()</tt> as well as <tt>push_back()</tt>, <tt>front()</tt> and <tt>pop_front()</tt>.
Epilogue html markup shown when solved	remove
Public permissions	remove
Remarks Comments, history, license, etc.	remove
Engine
Choices json list of string, bool pairs e.g. `[["good", true], ["bad", false]]`
Correct answer
Template / Reference solution
Template / Reference solution	#include <iostream> #include <deque> using namespace std; // ASSUMING a and b are sorted in increasing order, return a new queue // consisting of the elements of both in combined increasing order deque<int> merge(deque<int> a, deque<int> b) { deque<int> result; // keep going as long as there are elements to merge in BOTH while (\[!a.empty() && !b.empty()]\) { // take the smaller element from either a or b, move it to result \[ if (b.front() < a.front()) { result.push_back(b.front()); b.pop_front(); } else { result.push_back(a.front()); a.pop_front(); } ]\ } // if anything is left over once one queue is empty, move it into result \[ while (!a.empty()) { result.push_back(a.front()); a.pop_front(); } while (!b.empty()) { result.push_back(b.front()); b.pop_front(); } ]\ return result; } // return a new queue consisting of the same elements in sorted order deque<int> merge_sort(deque<int> input) { if (input.size() == 1) { // base case \[ return input; ]\ } else { // move half the elements into a new queue \[ int halfSize = input.size() / 2; deque<int> firstHalf; for (int i=0; i<halfSize; i++) { firstHalf.push_back(input.front()); input.pop_front(); } ]\ // sort both halves and merge return \[merge(merge_sort(firstHalf), merge_sort(input))]\; } } // read all integers from input, sort them, and print them int main(int argc, char* argv[]) { deque<int> data; int value; while (cin >> value) data.push_back(value); deque<int> sortedData = merge_sort(data); while (!sortedData.empty()) { cout << sortedData.front() << " "; sortedData.pop_front(); } }
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 `[{}]`	[ {"stdin": "9 1 6 2"}, {"stdin": "3 7 8 2 4 5 2 4 1"}, {"stdin": "29 48 72 90 53 31 81 8 12 71 9 42 46 76 36 59 75 7 18 74 67 40 98 30 63 11 24 91 64 6 75 26 95 26 79 43 2 65 21 9 28 46 29 8 23 72 78 28 12 51 32 70 80 25 95 27 26 41 62 80 6 1 60 97 83 64 30 33 42 33 41 46 9 24 96 12 71 56 11 42 25 22 53 92 83 62 44 43 63 58 16 28 69 20 20 70 65 53 93 33"} ]
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'.