CODEWITHSUNDEEP
c++arraysmerge
khguru13
khguru13

Reputation: 1

Merging two arrays in ascending order (both arrays are same size)

My friend and I are struggling with a merging function. It requires that both arrays have the same size, thus the merged array twice the number. This is what we have so far:

void mergeTwoSortedArrays(const int a1[], const int a2[], int mergedArray[], int n) 
{
    int i = 0;
    int j = 0;
    int k = 0;

    while (i <= n && j <= n) 
    {
        if (a1[i] == a2[j]) 
        {
            mergedArray[k] = a1[i];
            mergedArray[k] = a2[j];
            i++;
            j++;
        }
        k++;
    }
}

It's not working however. Any tips?

Upvotes: 0

Views: 15492

Answers (3)

kfsone
kfsone

Reputation: 24249

I don't know if you're trying to merge them as in interleave them or just concatenate two distinct arrays. If it's striding:

#include <iostream>

void mergeTwoArraysIntoOne(const int* lhs, const int* rhs, int* dst, size_t numElements) {
    const int* const endLhs = lhs + numElements;
    const int* const endRhs = rhs + numElements;
    for ( ; lhs < endLhs ; ) {
        while (rhs < endRhs && *rhs < *lhs)
            *(dst++) = *(rhs++);
        *(dst++) = *(lhs++);
    }
    while (rhs < endRhs)
        *(dst++) = *(rhs++);
}

void dumpArray(int* array, size_t elements) {
    for (size_t i = 0; i < elements; ++i)
        std::cout << array[i] << " ";
    std::cout << std::endl;
}

int main() {
    int array1[] = { 1, 2, 3 };
    int array2[] = { 10, 20, 30 };
    int array3[] = { 1, 11, 31 };

    int result[6];

    mergeTwoArraysIntoOne(array1, array2, result, 3);
    dumpArray(result, 6);

    mergeTwoArraysIntoOne(array2, array1, result, 3);
    dumpArray(result, 6);

    mergeTwoArraysIntoOne(array1, array3, result, 3);
    dumpArray(result, 6);

    mergeTwoArraysIntoOne(array3, array1, result, 3);
    dumpArray(result, 6);

    mergeTwoArraysIntoOne(array2, array3, result, 3);
    dumpArray(result, 6);

    mergeTwoArraysIntoOne(array3, array2, result, 3);
    dumpArray(result, 6);

    return 0;
}

Live demo: http://ideone.com/7ODqWD

If it's just concatenating them:

std::copy(&lhs[0], &lhs[numElements], &dst[0]);
std::copy(&rhs[0], &rhs[numElements], &dst[numElements]);

Upvotes: 0

Ashok
Ashok

Reputation: 6244

This is what i came up with - 

void mergeTwoSortedArrays(const int a1[], const int a2[], int mergedArray[], int n) {

    int i = 0;
    int j = 0;
    int k = 0;

    // Iterate and compare two input arrays until at least one of them reaches to boundary. 
    while (i < n && j < n) {
        if (a1[i] < a2[j]) {
            mergedArray[k++] = a1[i++];
        }
        else if (a1[i] > a2[j]) {
            mergedArray[k++] = a2[j++];
        }
        else if (a1[i] == a2[j]) {
            mergedArray[k++] = a1[i++];
            mergedArray[k++] = a2[j++];
        }
    }

    // Copy the remaining items from the other array, without comparison until, boundary.
    while (i < n) mergedArray[k++] = a1[i++];
    while (j < n) mergedArray[k++] = a2[j++];

}

Upvotes: 0

paddy
paddy

Reputation: 63471

Is this for merge sort or something? The usual approach is to do the combined merge, much like you have done already, followed by a copy. Here's the first part. You were a little confused. Read through this and you'll see it makes sense:

while (i < n && j < n) {
    if (a1[i] <= a2[j]) {
        mergedArray[k++] = a1[i++];
    } else {
        mergedArray[k++] = a2[j++];
    }
}

Then you handle the remaining elements. Obviously the loop finishes when only one array reaches the end. So now you need two much simpler loops. Only one will execute - no need for complicated tests:

while (i < n) mergedArray[k++] = a1[i++];
while (j < n) mergedArray[k++] = a2[j++];

I turned your tests into < instead of <=, because the arrays are zero-based.

Upvotes: 4

Related Questions