NicholasAdamou

Problem 1: Merge two sorted arrays

Sep 13th, 2019
364
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.77 KB | None | 0 0
  1. import java.util.Arrays;
  2.  
  3. public class Main {
  4.     // Give two sorted arrays of the integers, write a function to merge these two arrays.
  5.     // Both arrays can have duplicate elements.
  6.     // EXPECTED OUTPUT: { -12, -6, 5, 11, 12, 17, 21, 25, 33, 39, 41, 41, 44, 49, 50, 50 }
  7.     public static void main(String[] args) {
  8.         int[] a = { 12, 25, 33, 41, 50 };
  9.         int[] b = { -12, -6, 5, 11, 17, 21, 39, 41, 44, 49, 50 };
  10.  
  11.         // STEP 1: Create an array c[] of size a + b.
  12.         int[] c = new int[a.length + b.length];
  13.  
  14.         mergeArrays(a, b, a.length, b.length, c);
  15.  
  16.         System.out.println("EXPECTED OUTPUT: [-12, -6, 5, 11, 12, 17, 21, 25, 33, 39, 41, 41, 44, 49, 50, 50]");
  17.         System.out.println("ACTUAL OUTPUT: " + Arrays.toString(c));
  18.     }
  19.  
  20.     // Merge a[0..n1-1] and b[0..n2-1]
  21.     // into c[0..n1+n2-1].
  22.     private static void mergeArrays(int[] a, int[] b, int n1, int n2, int[] c) {
  23.         int i = 0, j = 0, k = 0;
  24.  
  25.         // STEP 2: Copy all n1 elements of a[] to c[].
  26.         //  - Pick smaller of current elements in a[] and b[],
  27.         //    copy this smaller element to next position in c[]
  28.         //    and move ahead in c[] and the array whose element is picked.
  29.  
  30.         // Traverse both array
  31.         while (i < n1 && j < n2) {
  32.             // Check if current element of first
  33.             // array is smaller than current element
  34.             // of second array. If yes, store first
  35.             // array element and increment first array
  36.             // index. Otherwise do same with second array.
  37.             if (a[i] < b[j]) {
  38.                 c[k++] = a[i++];
  39.             } else {
  40.                 c[k++] = b[j++];
  41.             }
  42.         }
  43.  
  44.         // STEP 3: Traverse b[] and one by one insert elements (like insertion sort) of c[] to a[].
  45.  
  46.         // Store remaining elements of first array
  47.         while (i < n1) {
  48.             c[k++] = a[i++];
  49.         }
  50.  
  51.         // Store remaining elements of second array
  52.         while (j < n2) {
  53.             c[k++] = b[j++];
  54.         }
  55.     }
  56. }
Advertisement
Add Comment
Please, Sign In to add comment