4
\$\begingroup\$

Any suggestions for improvement are welcome.

public static int[] concatArrays(int[] a1, int[] a2) {
    int n1 = a1.length;
    int n2 = a2.length;
    if(n1 == 0) return a2;
    if(n2 == 0) return a1;

    int n = n1 + n2;
    int counter = 0;
    int[] result = new int[n];
    for(; counter < n1; counter++) {
        result[counter] = a1[counter];
    }
    for(; counter < n; counter++) {
        result[counter] = a2[counter - n1];
    }
    return result;
}

public static int[] concatArrays(int[] a1, int a2) {
    int[] a2New = new int[] {a2};
    return concatArrays(a1, a2New);
}



public static int[] sort(int[] data) {
    if(data.length == 0) return new int[0];
    int nBefore = 0;
    int nAfter = 0;
    int[] beforeArray = new int[data.length];
    int[] afterArray  = new int[data.length];
    for(int i = 1; i < data.length; i++) {
        if(data[i] < data[0]) {
            beforeArray[nBefore++] = data[i];
        }
        else {
            afterArray[nAfter++] = data[i];
        }
    }
    int[] beforeArrayTrimmed = new int[nBefore];
    int[] afterArrayTrimmed = new int[nAfter];
    System.arraycopy(beforeArray, 0, beforeArrayTrimmed, 0, nBefore);
    System.arraycopy(afterArray, 0, afterArrayTrimmed, 0, nAfter);
    return concatArrays(
            concatArrays(sort(beforeArrayTrimmed), data[0]),
            sort(afterArrayTrimmed)
    );
}
\$\endgroup\$
3
\$\begingroup\$

Your Quick sort will not be as quick as most quicksorts are designed to be.

Your code is continually creating, populating, and discarding arrays of integers. Quick-sort algorithms will almost always have a single array and do the sorting 'in place'. This saves a huge amount of copy overhead.

In fact, your copy overhead is making the system run many, many times slower as you copy data from one array to another.

Since this answer is essentially saying "you're doing it wrong", it's not really a code review, but, you should read up on how others have done a quick sort. References I recommend are:

Additionally, you should read up on the standard array handling available in the Java libraries. Your code here (completely unnecessary if you do an in-place quick sort):

public static int[] concatArrays(int[] a1, int[] a2) {
    int n1 = a1.length;
    int n2 = a2.length;
    if(n1 == 0) return a2;
    if(n2 == 0) return a1;

    int n = n1 + n2;
    int counter = 0;
    int[] result = new int[n];
    for(; counter < n1; counter++) {
        result[counter] = a1[counter];
    }
    for(; counter < n; counter++) {
        result[counter] = a2[counter - n1];
    }
    return result;
}

Can easily be reduced to:

public static int[] concatArrays(int[] a1, int[] a2) {
    int[] result = Arrays.copyOf(a1, a1.length + a2.length);
    System.arrayCopy(a2, 0, result, a1.length, a2.length);
    return result;
}
\$\endgroup\$
  • \$\begingroup\$ Your code is not equivalent in case one array is empty as it always copies (This is usually better, but slower). \$\endgroup\$ – maaartinus Jan 28 '15 at 4:54
4
\$\begingroup\$

Using counter for both for loops seems awkward.

for(int i = 0; i < n1; i++) {
    result[i] = a1[i];
}
for(int i = 0; i < n2; i++) {
    result[n1 + i] = a2[i];
}

This way, the for loop looks just like people expect it to look. Your implementation requires extra thought. There is still a single arithmetic operation for indexing in the second loop, so reusing counter is not saving you anything.


One line if statements can be missed by someone reading your code. Plus you need to remember to add curly brackets if you want to add a second line.


concatArrays(int[] a1, int a2) does not concatenate arrays. Function names that lie about what they do are bad.

\$\endgroup\$
2
\$\begingroup\$

When concatenating arrays, it would be more efficient to use System.arraycopy just like you did it in sort. That will also eliminate the reused counter variable, which is a bad practice anyway, as @unholysampler already pointed out.

It could be a good idea to create a helper method for trimming an array, to avoid some code duplication and potential mistakes.

It would be slightly better to organize these statement like this:

int n1 = a1.length;
if(n1 == 0) return a2;
int n2 = a2.length;
if(n2 == 0) return a1;

Because if the first array is empty, there's no need to get the length of the second.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.