Comparing two (almost identical) implementations of Insertion Sort; one of them fails

52 views Asked by At

Basically I replaced n with aData[i] in the Non-working implementation. Am I missing something fundamentally wrong? The Second implementation fails on the same TEST Data.

Passing implementation:

static long[] sort(long[] aData) {
    for (int i = 1; i < aData.length; i++) {
        long n = aData[i];

        int j = i - 1;
        while (j >= 0 && aData[j] > n) {
            aData[j + 1] = aData[j];
            j--;
        }
        aData[j + 1] = n;
    }
    return aData;
}

Failing implementation:

static long[] sort(long[] aData) {
    for (int i = 1; i < aData.length; i++) {
        int j = i - 1;
        while (j >= 0 && aData[j] > aData[i]) {
            aData[j + 1] = aData[j];
            j--;
        }
        aData[j + 1] = aData[i];
    }
    return aData;
}
1

There are 1 answers

0
assylias On BEST ANSWER

In the first iteration of the while loop, j + 1 == i. So when you write aData[j + 1] = aData[j], you change the value of aData[i] within the loop.

In the initial version, n is constant throughout the operation. Also note that using aData[i] instead of n is very unlikely to improve performance (if anything, it will probably be slower).