MERGING - SOLUTION
#include <iostream>using namespace std;
int main()
{
int m,n,k;
cin>>m;
int A[m];
for(int i=0;i<m;i++){
cin>>A[i];
}
cin>>n;
int B[n];
k=m+n;
int C[k];
for(int i=0;i<n;i++){
cin>>B[i];
}
for(int i=0,p=0;i<m+n;i++){
if(i<m){
C[i]=A[i];
}
else{
C[i]=B[p++];
}
}
/* for(int i=0;i<k;i++){
cout<<C[i]<<endl;;
}*/
int j;
for(int i=1;i<k;i++){
int b=C[i];
for(j=i-1;j>=0;j--){
if(C[j]>b){
C[j+1]=C[j];
}
else{
break;
}
}
C[j+1]=b;
}
// cout<<"Sortiran:"<<endl;
for(int i=0;i<k;i++){
cout<<C[i]<<endl;
}
return 0;
}
Task description
The task is to merge two sorted arrays of numbers into one, which must also be sorted. This is a common problem of merging sorted arrays.
Explanation of the code
- Entering the data:
- The program reads the number of students in group A (m), then m numbers (the points of the students from group A).
- Then it reads the number of students in group B (n), then n numbers (the points of the students from group B).
- Initializing and entering the arrays:
cin >> m;
int A[m];
for (int i = 0; i < m; i++) {
cin >> n;
int B[n];
for (int i = 0; i < n; i++) {
Here two arrays A and B are entered, with m and n elements respectively. Each array is already sorted.int A[m];
for (int i = 0; i < m; i++) {
cin >> A[i];
}cin >> n;
int B[n];
for (int i = 0; i < n; i++) {
cin >> B[i];
}Combining and sorting
The program combines arrays A and B into one array C:
int k = m + n;
int C[k];
for (int i = 0; i < m; i++) {
for (int i = 0, p = 0; i < n; i++) {
Then array C is sorted with insertion sort:int C[k];
for (int i = 0; i < m; i++) {
C[i] = A[i];
}for (int i = 0, p = 0; i < n; i++) {
C[m + i] = B[i];
}
int j;
for (int i = 1; i < k; i++) {
Printing the result:for (int i = 1; i < k; i++) {
int b = C[i];
for (j = i - 1; j >= 0 && C[j] > b; j--) {
C[j + 1] = b;
}for (j = i - 1; j >= 0 && C[j] > b; j--) {
C[j + 1] = C[j];
}C[j + 1] = b;
for (int i = 0; i < k; i++) {
cout << C[i] << endl;
}
A comment on the code
The code is almost correct, but there is a weakness in how the arrays are combined. The “merging sorted lists” method should be used instead of sorting the whole array after combining, because the input arrays are already sorted.
Optimization:
Since the input arrays are already sorted, you can use a more efficient merging algorithm, which is O(m + n), instead of the O((m + n)²) used in the current code. This can be done using two pointers to go through arrays A and B.
Optimized code
#include < iostream >
using namespace std;
int main() {
using namespace std;
int main() {
int m, n;
cin >> m;
int A[m];
for (int i = 0; i < m; i++) {
cin >> n;
int B[n];
for (int i = 0; i < n; i++) {
int i = 0, j = 0;
while (i < m && j < n) {
while (i < m) {
while (j < n) {
return 0;
}cin >> m;
int A[m];
for (int i = 0; i < m; i++) {
cin >> A[i];
}cin >> n;
int B[n];
for (int i = 0; i < n; i++) {
cin >> B[i];
}int i = 0, j = 0;
while (i < m && j < n) {
if (A[i] <= B[j]) {
}
cout << A[i++] << endl;
} else {
cout << B[j++] << endl;
}while (i < m) {
cout << A[i++] << endl;
}while (j < n) {
cout << B[j++] << endl;
}return 0;
Explanation of the optimized code
- Initialization and input: Entering the data is the same as in the first code.
- Merging and printing:
- We use two pointers i and j to go through arrays A and B.
- We compare the current elements and print the smaller one, until one of the arrays is used up.
- After that, we print the remaining elements from the remaining arrays.
Example "Merging"-solution
#include <iostream>using namespace std;
/*
int main()
{
int m,n,k;
cin>>m;
int A[m];
for(int i=0;i<m;i++){
cin>>A[i];
}
cin>>n;
int B[n];
k=m+n;
int C[k];
for(int i=0;i<n;i++){
cin>>B[i];
}
for(int i=0,p=0;i<m+n;i++){
if(i<m){
C[i]=A[i];
}
else{
C[i]=B[p++];
}
}
/* for(int i=0;i<k;i++){
cout<<C[i]<<endl;;
}*/
int j;
for(int i=1;i<k;i++){
int b=C[i];
for(j=i-1;j>=0;j--){
if(C[j]>b){
C[j+1]=C[j];
}
else{
break;
}
}
C[j+1]=b;
}
// cout<<"Sorted:"<<endl;
for(int i=0;i<k;i++){
cout<<C[i]<<endl;;
}
return 0;
}
edit.
© 2019 by Slobodan izprogramiranja.weebly.com
All rights reserved
