I'm trying to write an insertion sort method, and I have managed to finish it, but I don't understand why my first version cannot work correctly.
Here's my first attempt:
public static void insertionSort(int[] list) {
for (int i = 1; i < list.length; i++) {
int current = list[i];
for (int k = i - 1; k >= 0 && current < list[k]; k--) {
list[i] = list[k];
list[k] = current;
}
}
}
public static void main(String[] args) {
int[] list = {8, 22, 90, 10};
insertionSort(list);
}
My output for the above code is: 8, 10, 10, 22
But the answer would be correct if the inside for-loop, at line 5, is changed from: list[i] = list[k];
to: list[k + 1] = list[k];
To my understanding, k + 1
is equal to i
, but it must be different in loop counting and I can't figure out how. I have tried many sets of input, and only values that lie between the range of the 2 first indexes (in this case 8 and 22) would be incorrect.