Reputation: 63
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
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
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
Reputation: 716
this code should follow a simple logic of
Upvotes: 2
Reputation: 726809
A common solution to this issue is replacing a single loop with three:
A
, if any, into the output arrayB
, if any, into the output arrayThis 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
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