Jon Wong
Jon Wong

Reputation: 63

Merging sorted arrays of unequal length

I have a project that requires me to merge two, sorted arrays (a and b) and place the result in a new array of length a.length + b.length. I'm tracking both the counter of my placement in all 3 arrays, and the length of my arrays are unequal. My convention is that if one array runs out before another, the code will just dump the rest of the other array into the result array.

Unfortunately, the only way that I can check if the other array still contains elements is seen the for loop.

Can anyone help me? This should a relatively easy fix, but I can't think of a solution.

public class Two {
    public static void main(String[] args) {
        //sample problem
        int[] var_a = {2,3,5,5,8,10,11,17,18,20}; 
        int[] var_b = {5,6,7,8,14,15,17};
        final int a_size = 10;
        final int b_size = 7;
        final int c_size = 17; 
        int[] var_c = new int[17];

        int aCount = 0;
        int bCount = 0;
        int cCount = 0;
        for (cCount = 0; cCount < c_size; cCount++) {
            //b runs out before a runs out
            if ((bCount == b_size) && (aCount <= a_size)) {
                //dump rest of var_a into var_c     
                var_c[cCount] = var_a[aCount];
                aCount++;
            }
            //PROBLEM: bCount is equal to bSize, and is triggering the break.
            //a runs out before b runs out
            else if ((aCount == a_size) && (bCount <= b_size)) {
                //dump rest of var_b into var_c
                var_c[cCount] = var_b[bCount];
                bCount++;
            }

            if ((aCount >= a_size) || (bCount >= b_size) || (cCount >= c_size)) {break;}

            if (var_a[aCount] < var_b[bCount]) {
                var_c[cCount] = var_a[aCount];
                aCount++;
            } else if (var_a[aCount] > var_b[bCount]) {
                var_c[cCount] = var_b[bCount];
                bCount++;
            } else if (var_a[aCount] == var_b[bCount]) {
                var_c[cCount] = var_a[aCount];
                aCount++;
                cCount++;
                var_c[cCount] = var_b[bCount];
                bCount++;
            }
        }
        for (int i : var_c) {
            System.out.print(i + " ");
        }
    }
}

Upvotes: 6

Views: 1478

Answers (5)

Buurman
Buurman

Reputation: 1984

Your algorithm looks basically correct. Without running through the exact code I think your problem is mostly that you have too many equalities, ie just about every comparison you have is equals, lessthanorequals, greaterthanorequals.

If a==b, then also a<=b and a>=b. Too many of your if statements match because of this. Keep a close eye on what the specific indexes should be and limit your cases to what they exactly should be.

I've rewritten your code (without an editor, sorry, so it might not work out of the box) which should give you a pretty good idea.

public class Two 
{
    public static void main(String[] args) 
    {
        //sample problem
        int[] arrayA = {2,3,5,5,8,10,11,17,18,20}; 
        int[] arrayB = {5,6,7,8,14,15,17};
        final int sizeA = arrayA.length();
        final int sizeB = arrayB.length();
        final int sizeC = sizeA+sizeB; 
        int[] arrayC = new int[sizeC];
        int countA = 0;
        int countB = 0;
        int countC = 0;
        for (countC = 0; countC < sizeC; countC++)
        {
            // if a has run out, fill with b
            if (countA == sizeA && countB < sizeB)
            {
                arrayC[countC] = arrayB[countB];
                countB++;
            }
            // if b has run out, fill with a
            else if (countA < sizeA && countB == sizeB)
            {
                arrayC[countC] = arrayA[countA];
                countA++;
            }
            // countA < sizeA && countB < sizeB because 
            // if countA == sizeA && countB == sizeB then also countC == sizeC 
            // and the for-loop would have stopped.
            else        
            {
                // mind, if arrayA[countA] == arrayB[countB] then first 
                // a will be added and on the next pass b will be added
                if (arrayA[countA] <= arrayB[countB])
                {
                    arrayC[countC] = arrayA[countA];
                    countA++;
                }
                else
                {
                    arrayC[countC] = arrayB[countB];
                    countB++;
                }
            }
        }
    }
}

Upvotes: 1

Luke Melaia
Luke Melaia

Reputation: 1468

This is probably what you want:

void doArrayThing(){
    //the two arrays containing the elements
    int[] array1 = {1, 3, 5, 2, 7, 5};
    int[] array2 = {3, 6, 2, 8};

    //the length of the 2 arrays
    int arrayLength1 = array1.length;
    int arrayLength2 = array2.length;

    //the length of both the arrays
    int containerArrayLength = arrayLength1 + arrayLength2;

    //the array that holds all the elements
    int[] container = new int[containerArrayLength];

    //a for loop that adds the first array elements
    for(int i = 0; i < arrayLength1; i++){
        //add the elements of the first array
        container[i] = array1[i];
    }

    //the for loop that adds the second array elements
    for(int i = 0; i < arrayLength2; i++){
        //add the second array elements on top of the first
        container[i + arrayLength1] = array2[i];
    }

    for(int i = 0; i < containerArrayLength; i++){
        //print all the elements
        System.out.println(container[i]);
    }
}

What it does:

It iterates over the first array and adds the numbers, then iterates over the second array and adds the elements on top of the first arrays elements.

Upvotes: 1

notrai
notrai

Reputation: 716

this code should follow a simple logic of

  1. initialize counters to 0 for all 3 a_counter, b_counter, c_c
  2. now while till a_c or b_counter are less than a_size and b_size respectively
    • compare a[a_counter] with b[b_counter] and add the smaller to c at c[c_counter]
    • increment c_counter, and which ever was chosen above
    • repeat
  3. once out of loop, one of a or b is over
    • keep adding to c all the remaining elements of a if b is over; or b if a is over I trust you don't need the code, just improvement in logic; so not giving the code.

Upvotes: 2

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726809

A common solution to this issue is replacing a single loop with three:

  • First loop merges the two arrays until one of them runs out of elements
  • Second loop dumps the remaining elements of array A, if any, into the output array
  • Third loop dumps the remaining elements of array B, if any, into the output array

This structure allows you to make the merge loop a lot simpler:

while (aCount != var_a.length() && b.Count != var_b.length()) {
    ... // merge
}
while (aCount != var_a.length()) {
    var_c[cCount++] = var_a[aCount++];
}
while (bCount != var_b.length()) {
    var_c[cCount++] = var_b[bCount++];
}

Note that of the last two loops at most one will be executed. Also note the use of length() method to determine the length of the array. It is more reliable than setting up a_size, b_size, and so on.

Upvotes: 3

Eran
Eran

Reputation: 393936

Instead of iterating over the indices of the merged array, you can iterate over the indices of the individual arrays, to makes sure you never get out of bounds :

int aCount = 0;
int bCount = 0;
int cCount = 0;
while (aCount < var_a.length && bCount < var_b.length) {
    if (var_a[aCount] <= var_b[bCount]) {
        var_c[cCount++] = var_a[aCount++];
    } else {
        var_c[cCount++] = var_b[bCount++];
    }
}
// now add what remains of var_a or var_b
while (aCount < var_a.length)
    var_c[cCount++] = var_a[aCount++];
while (bCount < var_b.length)
    var_c[cCount++] = var_b[bCount++];

Upvotes: 1

Related Questions