Combining sorted arrays of unequal length

Question

I have a project that requires me to combine two sorted arrays (a and b) and put the result in a new array of length a.length + b.length. I track both the counter of my placement in all three arrays, and the length of my arrays is unequal. My convention is that if one array ends before another, the code will simply upload the rest of the other array to the results array.

Unfortunately, the only way to check if another array still contains elements is with a for loop.

Can anyone help me? This should be relatively easy to fix, but I cannot come up with 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 + " "); } } } 

Answer 1

A common solution to this problem is to replace one cycle with three:

• The first loop combines two arrays until one of them finishes the elements
• The second loop dumps the remaining elements of array A , if any, into the output array
• The third loop dumps the remaining elements of array B , if any, into the output array

This structure makes the merge cycle much easier:

 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++]; } 

Please note that from the last two cycles no more than one will be executed. Also note the use of the length() method to determine the length of the array. It is more reliable than setting a_size , b_size , etc.

Answer 2

this code should follow simple logic

• initialize counters to 0 for all 3 a_counter, b_counter, c_c
• now while a_c or b_counter is less than a_size and b_size respectively
  • compare [a_counter] with b [b_counter] and add a lower c value to c [c_counter]
  • increment c_counter and which has ever been selected above
  • repeat
• once out of a loop, one of a or b completed
  • continue to add to c all other elements of a if b is completed; or b, if a I hope you do not need code, just an improvement in logic; therefore without specifying a code.

Answer 3

Instead of repeating the indices of a joined array, you can iterate over the indices of individual arrays so that you never go beyond:

 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++]; 

Answer 4

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 does he do:

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

Answer 5

Your algorithm looks basically correct. Without missing the exact code, I think that your problem is mainly that you have too many equalities, i.e. almost every comparison you have is equal to lessthanorequals, morethanorequals.

If a == b, then also a <= b and a> = b. Because of this, there are too many of your if statements. Keep track of what specific indexes should be, and limit your affairs to what they definitely should be.

I rewrote your code (without an editor, sorry, so it may not work out of the box), which should give you a 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++; } } } } }