Question

Hi i have this for a practical tomorrow (C++):

a) Write a function vector merge(vector a, vector b) that merges two vectors, alternating elements from both vectors. If one vector is shorter than the other, then alternate as long as you can and then append the remaining elements from the longer vector.

For example, if a is 1 4 9 16 and b is 9 7 4 9 11

Then merge returns the vector 1 9 4 7 9 4 16 9 11

b) Write a function vector merge_sorted(vector a, vector b) that merges two sorted vectors, producing a new sorted vector. For example, if a is 1 4 9 16 and b is 9 7 4 9 11 Then merge_sorted returns the vector 1 4 4 7 9 9 9 11 16

c) Write a procedure void pie_chart(vector data) that displays a pie chart of the values in data, assuming that all values in data are positive.

d) Write the selection sort algorithm as a template function, which can sort both numeric and string data types.

Answer 1

The language used is C++.

(a) Function:

vector<int> merge(vector<int> a, vector<int> b) {

vector<int> result;
int n = max(a.size(), b.size());

for(int i=0;i<n;i++) {
result.push_back(a[i]);
result.push_back(b[i]);
}

for(int i=n;i<a.size();i++) {
result.push_back(a[i]);
}

for(int i=n;i<b.size();i++) {
result.push_back(b[i]);
}

return result;
}

(b) Function:

vector<int> merge_sorted(vector<int> a, vector<int> b) {
vector<int> result;

int i = 0;
int j = 0;

while(i < a.size() && j < b.size()) {
if(a[i] <= b[j]) {
result.push_back(a[i]);
i++;
} else {
result.push_back(b[j]);
j++;
}
}

for(int k=i;k<a.size();k++) {
result.push_back(a[k]);
}

for(int k=j;k<b.size();k++) {
result.push_back(b[k]);
}

return result;
}

(c) Function:

//Pie chart will not be drawn in code blocks
//Therefore, displaying the percentage of occurences of a number.
void pie_chart(vector<int> data) {
unordered_map<int, int> m;
for(int i=0;i<data.size();i++) {
m[data[i]]++;
}

unordered_map<int, int>::iterator it = m.begin();

while(it != m.end()) {
double percentage = (it->second*100.0)/data.size();
cout<<it->first<<" ----> "<<percentage<<"%"<<endl;
it++;
}
}

(d) Function:

template <typename T>
void selectionSort(vector<T> & arr) {

int n = arr.size();
for (int i = 0; i < n-1; i++) {

int min_index = i;
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[min_index])
min_index = j;
}

swap(arr[min_index], arr[i]);
}
}

Complete Code:

#include<bits/stdc++.h>
using namespace std;

vector<int> merge(vector<int> a, vector<int> b) {

vector<int> result;
int n = max(a.size(), b.size());

for(int i=0;i<n;i++) {
result.push_back(a[i]);
result.push_back(b[i]);
}

for(int i=n;i<a.size();i++) {
result.push_back(a[i]);
}

for(int i=n;i<b.size();i++) {
result.push_back(b[i]);
}

return result;
}

vector<int> merge_sorted(vector<int> a, vector<int> b) {
vector<int> result;

int i = 0;
int j = 0;

while(i < a.size() && j < b.size()) {
if(a[i] <= b[j]) {
result.push_back(a[i]);
i++;
} else {
result.push_back(b[j]);
j++;
}
}

for(int k=i;k<a.size();k++) {
result.push_back(a[k]);
}

for(int k=j;k<b.size();k++) {
result.push_back(b[k]);
}

return result;
}

//Pie chart will not be drawn in code blocks
//Therefore, displaying the percentage of occurences of a number.
void pie_chart(vector<int> data) {
unordered_map<int, int> m;
for(int i=0;i<data.size();i++) {
m[data[i]]++;
}

unordered_map<int, int>::iterator it = m.begin();

while(it != m.end()) {
double percentage = (it->second*100.0)/data.size();
cout<<it->first<<" ----> "<<percentage<<"%"<<endl;
it++;
}
}

template <typename T>
void selectionSort(vector<T> & arr) {

int n = arr.size();
for (int i = 0; i < n-1; i++) {

int min_index = i;
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[min_index])
min_index = j;
}

swap(arr[min_index], arr[i]);
}
}

//Main method
int main() {

vector<int> x{1, 7, 2, 4, 9, 16};
vector<int> y{4, 3, 9, 11};
vector<int> z = merge(x, y);

cout<<"merge is:\n";
for(int v : z) {
cout<<v<<" ";
}
cout<<endl;

vector<int> a{1, 4, 9, 16};
vector<int> b{4, 7, 9, 9, 11};
vector<int> res = merge_sorted(a, b);

cout<<"Sorted merge is:\n";
for(int v : res) {
cout<<v<<" ";
}
cout<<endl;

pie_chart(b);

vector<string> d {"def", "xyz", "abc"};
selectionSort(d);

for(string s : d) {
cout<<s<<" ";
}

}

Code Snippets:

Sample Output: