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;
}
In the first iteration of the while loop,
j + 1 == i
. So when you writeaData[j + 1] = aData[j]
, you change the value ofaData[i]
within the loop.In the initial version,
n
is constant throughout the operation. Also note that usingaData[i]
instead ofn
is very unlikely to improve performance (if anything, it will probably be slower).