Merge two sorted arrays-CodePudding

This is my code for merging 2 sorted arrays:

#include<iostream>

using namespace std;

void merge(int arr1[], int n, int arr2[], int m, int arr3[]) {

    int i = 0, j = 0;
    int k = 0;
    while( i<n && j<m) {
        if(arr1[i] < arr2[j]){
            arr3[k  ] = arr1[i  ];
        }
        else{
            arr3[k  ] = arr2[j  ];
        }
    }
    
}

void print(int ans[], int n) {
    for(int i=0; i<n; i  ) {
        cout<< ans[i] <<" ";
    }
    cout << endl;
}

int main() {

    int arr1[5] = {1,3,5,7,9};
    int arr2[3] = {2,4,6};

    int arr3[8] = {0};

    merge(arr1, 5, arr2, 3, arr3);

    print(arr3, 8);


    return 0;
}

I expect to get the output:

1 2 3 4 5 6 7 9

But instead the output I get is:

1 2 3 4 5 6 0 0

What is the cause of that ?

CodePudding user response：

You need to handle the case where you reached the end of the shorter list, and need to copy the rest of the longer one.
This is handled in the code below by the 2 additional while loops.

Also it's advisable to use std::vectors instead of old c style arrays. It will save you the need to manually track the array sizes.

#include <iostream>
#include <vector>

void merge(std::vector<int> const & arr1, std::vector<int> const & arr2, std::vector<int> & arr3) {
    int i = 0, j = 0;
    int k = 0;
    arr3.resize(arr1.size()   arr2.size());
    while (i < arr1.size() && j < arr2.size()) {
        if (arr1[i] < arr2[j]) {
            arr3[k  ] = arr1[i  ];
        }
        else {
            arr3[k  ] = arr2[j  ];
        }
    }
    // Copy the rest of arr1 (if needed):
    while (i < arr1.size()) {
        arr3[k  ] = arr1[i  ];
    }
    // Copy the rest of arr2 (if needed):
    while (j < arr2.size()) {
        arr3[k  ] = arr2[j  ];
    }
}

void print(std::vector<int> const & ans) {
    for (size_t i = 0; i < ans.size(); i  ) {
        std::cout << ans[i] << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> arr1 = { 1,3,5,7,9 };
    std::vector<int> arr2 = { 2,4,6 };
    std::vector<int> arr3;
    merge(arr1, arr2, arr3);
    print(arr3);
    return 0;
}

Output:

1 2 3 4 5 6 7 9

A side note: better to avoid using namespace std - see here Why is "using namespace std;" considered bad practice?.

CodePudding user response：

this loop

while( i<n && j<m) {

stops when you reach the end of the shortest array. In this case, when m=3. You need to continue to copy the remaining elements from the larger array

CodePudding user response：

Assume for a second that there are "sentinel" values arr1[n] == arr2[m] == ∞. Then the code below would work, as it will fully traverse both arrays, without going past (mind the ||).

int i = 0, j = 0 k = 0;
while (i < n || j < m) {
    if (arr1[i] < arr2[j]) {
        arr3[k  ]= arr1[i  ];
    }
    else {
        arr3[k  ]= arr2[j  ];
    }
}

Now you can emulate the presence of the sentinels by refining the comparison condition:

arr1[i] < arr2[j]

becomes

(i < n && j < m && arr1[i] < arr2[j]) || (i < n && j >= m)

which can be written

i < n && (j >= m || arr1[i] < arr2[j])

(check the cases n == i and m == j).

Notice that it is more efficient to split the code in three successive loops, processing separately the situations where one of the arrays has been fully seen.

CodePudding user response：

You have to consider the edge case:- when one of the linked lists ends. Then you have to loop through the other list and add the remaining elements.

So in your case, arr2 has 3 values and arr1 has 5 values. So your while loop ends when one of the list elements ends. So in the above case, arr2 will end so you have to add arr1 elements in arr3

After a while loop, you have to add this code

    while (i < arr1.size()) arr3[k  ] = arr1[i  ];

    while (j < arr2.size()) arr3[k  ] = arr2[j  ];