combining and sorting two arrays Java?

Question

So basically there are two separate presorted arrays, and you have to combine them and sort them (without sort() methods of course). Here is my code:

public static void main(String[] args) {

    int a [] = {3,5,7,9,12,14, 15};
    int b [] = {6 ,7, 10};
    int j = 0;

    //output array should be 3,5,6,7,7,9,10,12,14,15

    int c [] = new int[a.length+b.length];//10 values

    for (int i = 0;i<b.length;i++){
        while(b[i]>a[j]){
            c[j] = a[j] ;
            j++;    
         }

        if(b[i] == a[j]){
            c[j] = b[i];
            c[j+1] = a[j];
        }

        c[j] = b[i];
        j++;
    }

    for(int i = 0;i<c.length;i++)
        System.out.println(c[i]);
    }

I'm guessing the zeros I am getting are from a mistake in one of the booleans (< & >), but I cant seem to figure it out. It works fine for the first 4, but once I get to the repeating 7's, it just goes crazy.

Please help me understand, don't just change the code.

Answer 1

This is how it should be in a simple way:

public static void main(String[] args) {

    int a [] = {3,5,7,9,12,14, 15};
    int b [] = {6 ,7, 10};
    int j = 0, k = 0;

    //output array should be 3,5,6,7,7,9,10,12,14,15

    int c [] = new int[a.length+b.length];//10 values

    // we're filling c with the next appropriate number
    // we start with checking a[0] and b[0] till we add
    // all the elements
    for (int i = 0; i < c.length; i++) {
        // if both "a" and "b" have elements left to check
        if (j < a.length && k < b.length) {
            // check if "b" has a smaller element
            if (b[k] < a[j]) {
                // if so add it to "c"
                c[i] = b[k];
                k++;
            }
            // if "a" has a smaller element
            else {
                // add it to "c"
                c[i] = a[j];
                j++;
            }       
        }
        // if there are no more elements to check in "a"
        // but there are still elements to check in "b"
        else if (k < b.length) {
            // add those elements in "b" to "c"
            c[i] = b[k];
            k++;
        }
        // if there are no more elements to check in "b"
        // but there are still elements to check in "a"
        else {
            // add those elements in "a" to "c"
            c[i] = a[j];
            j++;
        }
    }

    for(int i = 0; i < c.length; i++)
        System.out.println(c[i]);
}

Hope it helps.

Answer 2

You can try this code.

public static void main(String[] args) {
    int a[] = { 3, 5, 7, 9, 12, 14, 15 };
    int b[] = { 6, 7, 10 };

    // output array should be 3,5,6,7,7,9,10,12,14,15

    int alen = a.length;
    int blen = b.length;
    int c[] = new int[a.length + b.length];// 10 values

    int s[] = null;
    int[] l = null;

    if (alen < blen) {
        s = a;
        l = b;
    } else {
        s = b;
        l = a;
    }
            // Constructing Combined Array
    for (int i = 0, p = 0; i < c.length; i++, p++) {
        if (i == s.length) {
            p = 0;
        }
        if (i < s.length) {
            c[i] = s[p];
        } else {
            c[i] = l[p];
        }
    }
            //Sorting the C array 
    for (int i = 1; i < c.length; i++) {
        int j = i;
        int B = c[i];
        while ((j > 0) && (c[j - 1] > B)) {
            c[j] = c[j - 1];
            j--;
        }
        c[j] = B;
    }

    for (int i = 0; i < c.length; i++)
        System.out.print(c[i]);
}

Answer 3

Actually it's better to say merging (not combining) two arrays.

Simple algorithm (taken from this article) for merging sorted arrays A and B[0..n-1] into result C[0..m+n-1]:

1. Introduce read-indices i, j to traverse arrays A[0..m-1] and B, accordingly. Introduce write-index k to store position of the first free cell in the resulting array. By default i = j = k = 0.
2. At each step: if both indices are in range (i < m and j < n), choose minimum of (A[i], B[j]) and write it to C[k]. Otherwise go to step 4.
3. Increase k and index of the array, algorithm located minimal value at, by one. Repeat step 2.
4. Copy the rest values from the array, which index is still in range, to the resulting array.

Hope it helps.

Answer 4

Try this, your error is you are using the same cellular index for array A and array C:

public class MainClass {
      public static void main(String[] args) {
        int[] arrayA = { 23, 47, 81, 95 };
        int[] arrayB = { 7, 14, 39, 55, 62, 74 };
        int[] arrayC = new int[10];

        merge(arrayA, arrayA.length, arrayB, arrayB.length, arrayC);
        for (int i : arrayC) {
          System.out.println(i);

        }
      }

      public static void merge(int[] arrayA, int sizeA, int[] arrayB, int sizeB, int[] arrayC) {
        int arrayAIndex = 0, arrayBIndex = 0, arrayCIndex = 0;

        while (arrayAIndex < sizeA && arrayBIndex < sizeB)
          if (arrayA[arrayAIndex] < arrayB[arrayBIndex])
            arrayC[arrayCIndex++] = arrayA[arrayAIndex++];
          else
            arrayC[arrayCIndex++] = arrayB[arrayBIndex++];

        while (arrayAIndex < sizeA)
          arrayC[arrayCIndex++] = arrayA[arrayAIndex++];

        while (arrayBIndex < sizeB)
          arrayC[arrayCIndex++] = arrayB[arrayBIndex++];
      }
    }

This is another version

// size of C array must be equal or greater than
// sum of A and B arrays' sizes
public void merge(int[] A, int[] B, int[] C) {
      int i, j, k, m, n;
      i = 0;
      j = 0;
      k = 0;
      m = A.length;
      n = B.length;
      while (i < m && j < n) {
            if (A[i] <= B[j]) {
                  C[k] = A[i];
                  i++;
            } else {
                  C[k] = B[j];
                  j++;
            }
            k++;
      }
      if (i < m) {
            for (int p = i; p < m; p++) {
                  C[k] = A[p];
                  k++;
            }
      } else {
            for (int p = j; p < n; p++) {
                  C[k] = B[p];
                  k++;
            }
      }
}

Answer 5

Use ai and bi for the indices in both source arrays and ci as the index for the destination array.

You only need one loop.

Try to keep this very clear and advance in c by exactly one element at each iteration.

In the loop, check wether the end of one array was reached. If so, just take an element from the other array. Otherwise, take only the smaller element of a[ai] and b[bi] and increment the corresponding index.

It is very easy to make mistakes in mergesort (or in any code where two arrays need to be walked in parallel) by thinking "hey I can go along with a while loop instead of just doing a single if", but then you typically have two loops nested in a third one, and for each of the loops you have to do the right bounds checks, and there is typically no significant gain in performance.

p.s. Doing one main loop and then two cleanup loops after the main loop is fine, just avoid nested loops if they are not necessary, in particular in interviews where this may also cause confusion when calculating the runtime.

Answer 6

public class Combinearray {

    public static void main(String[] args) {
        int[] array1= {5,4,6,2,1};
        int[] array2= {2,5,8,4,1,6,4};
        int m=array1.length;
        int n=array2.length;
        int[] array3=new int[m+n];
        int a=1;
        for(int i=0;i<m;i++) {

            array3[i]=array1[i];//array1 is copied to array3
        }
        for(int i=0;i<n;i++) {
            array3[m-1+a]=array2[i];//array2 is copied to array3
            a++;
        }
        //array3 is combined array
         int l=array3.length;
            int temp[]=new int[l];
            for(int i=0;i<l;i++) {
                for(int j=i+1;j<l;j++) {
                    if(array3[i]>array3[j]) {
                        temp[i]=array3[i];
                        array3[i]=array3[j];
                        array3[j]=temp[i];
                    }
                }
            }
            System.out.println("sorted array is ");
            System.out.print("[");
            for(int i=0;i<l;i++) {
                System.out.print(array3[i]+" ");  
            }
            System.out.print("]");

    }

}