3
\$\begingroup\$

First post.

Can you please review my code and help me improve my coding. Please also suggest improvements if there is a miss in this post.

Problem Statement

Given two sorted arrays X[] and Y[] of size m and n each, merge elements of X[] with elements of array Y[] by maintaining the sorted order.
i.e. fill X[] with first m smallest elements and fill Y[] with remaining elements.

Input:
X[] = {1, 4, 7, 8, 10} , Y[] = {2, 3, 9}

Output:
X[] = {1, 2, 3, 4, 7} , Y[] = {8, 9, 10}

public static void main(String[] args) {
    int[] X = {11, 14, 17, 18, 110};
    int[] Y = {112, 113, 114};

    mergeRunner(X, Y);

    System.out.println("X: " + Arrays.toString(X));
    System.out.println("Y: " + Arrays.toString(Y));

}

private static void mergeRunner(int[] x, int[] y) {

    if (x[x.length - 1] > y[y.length - 1]) {
        merge(x, y);
    } else {
        merge(y, x);
    }

}

private static void merge(int[] x, int[] y) {
    final int m = x.length;
    final int n = y.length;

    int last = x[m - 1];
    int i = m - 2;
    for (int j = n - 1; j >= 0; j--) {

        while (i >= 0 && x[i] > y[j]) {
            i--;
        }

        //Insertion
        insertValue(x, i + 1, y[j]);

        y[j] = last;
        last = x[m - 1];

        //System.out.println("X: " + Arrays.toString(x));
        //System.out.println("Y: " + Arrays.toString(y));
    }

}

private static void insertValue(int[] x, int index, int valueToInsert) {

    int i = x.length - 1;
    while (i > index) {
        x[i] = x[i - 1];
        i--;
    }
    x[i] = valueToInsert;
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Welcome to Code Review, at the moment your code cannot be reviewed because it does not match the description of your task you provided, for further details you can check on-topic. \$\endgroup\$ Commented Aug 1, 2020 at 10:22
  • 2
    \$\begingroup\$ I have seen you edited your question so now description of the task and code match , for clarity I have edited your post separating description of the task from the code. \$\endgroup\$ Commented Aug 1, 2020 at 14:19

1 Answer 1

Reset to default
2
\$\begingroup\$

Your code is correct, but the problem you proposed can be solved in a less complicate manner, starting from your example these are some steps of my algorithm making comparisons between elements of the two arrays:

x = [1, 4, 7, 8, 10} , y = [2, 3, 9] step0 : comparing 10, 9
                  ^               ^

x = [1, 4, 7, 8, 9} , y = [2, 3, 10] step1 : 10, 9 swapped
                 ^                ^

x = [1, 4, 7, 8, 9} , y = [2, 3, 10] step2 : comparing 9, 3
                 ^            ^
       
x = [1, 4, 7, 8, 3} , y = [2, 9, 10] step3 : 3, 9 swapped 
                 ^            ^

x = [1, 3, 4, 7, 8} , y = [2, 9, 10] step5 : reordered x with swaps, comparing 8, 9
                 ^            ^

This means that if you start from the right of the two arrays, if the x array element is greater than the array y element, the swap will be done and after you will reorder the x array swapping adiacent elements if one element is smaller than previous element in the array.

With the help of a method to swap elements between the two arrays like this below:

private static void swap(int i, int j, int[] arr1, int[] arr2) {
    int tmp = arr1[i];
    arr1[i] = arr2[j];
    arr2[j] = tmp;
}

Your method mergeRunner can be rewritten like below:

private static void mergeRunner(int[] x, int[] y) {
    final int maxIndex = x.length - 1;

    for (int j = y.length - 1; j >= 0; --j) {

        if (y[j] < x[maxIndex]) {

            swap(maxIndex, j, x, y);

            for (int i = maxIndex; i > 0 && x[i - 1] > x[i]; --i) {

                swap(i, i - 1, x, x);
            }
        }
    }
}
\$\endgroup\$
4
  • \$\begingroup\$ (How did you assess correctness of your suggestion (disregarding the assumption y.length <= x.length)?) \$\endgroup\$ Commented Aug 3, 2020 at 5:01
  • \$\begingroup\$ @greybeard Hello, because the initial scenario includes the two sorted arrays and after every step of the algorithm the two arrays still remain always sorted indipendently from the fact I'm exchanging or not the elements (I'm will reorder the 'x' array in case of exchange). I'm not changing array initial dimensions m and n, so the algorithm brings the result expected by OP. \$\endgroup\$ Commented Aug 3, 2020 at 7:57
  • 1
    \$\begingroup\$ (I noticed you never change maxIndex (not having declared it const), got 2nd thoughts. Not very likely I'll look into this in earnest.) \$\endgroup\$ Commented Aug 3, 2020 at 8:37
  • \$\begingroup\$ @greybeard I got it, because the arrays are always ordered at every step I always compare y elements with the max element of x (x[maxIndex]) to do eventually a swap , I missed setting maxIndex to final, thanks for the advice. \$\endgroup\$ Commented Aug 3, 2020 at 8:51

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.