Consider this:
for (int i = 0; i < values.length; i++) {
if (i!=0 && values[i] < values[i - 1]) {
i
starts from 0, and then right after you use a condition i!=0
. You could simplify to:
for (int i = 1; i < values.length; i++) {
if (values[i] < values[i - 1]) {
Consider this:
if (values[i] < values[i - 1]) {
for (int j = i; j >= 1; j--) {
if (values[j] < values[j - 1]) {
// ...
} else break;
Notice that j
starts from i
, and you have the same if
immediately inside the loop, otherwise break. In other words, you don't need that outer if
, because you run the same thing immediately inside the loop.
Consider this:
for (int j = i; j >= 1; j--) {
if (values[j] < values[j - 1]) {
...
} else break;
an equivalent but shorter and more traditional way to write the same thing:
for (int j = i; j >= 1 && values[j] < values[j - 1]; j--) {
...
}
Putting it all together:
for (int i = 1; i < values.length; i++) {
for (int j = i; j > 0 && values[j] < values[j - 1]; j--) {
int temp = values[j - 1];
values[j - 1] = values[j];
values[j] = temp;
}
}
We have arrived at the pseudo algorithm of insertion sort in wikipedia ;-)
I recommend using unit tests to check your implementations instead of printing text to the console and checking with your eyes. For example:
public Integer[] sort(Integer[] orig) {
Integer[] values = orig.clone();
for (int i = 1; i < values.length; i++) {
for (int j = i; j > 0 && values[j] < values[j - 1]; j--) {
int temp = values[j - 1];
values[j - 1] = values[j];
values[j] = temp;
}
}
return values;
}
@Test
public void testExamples() {
Assert.assertArrayEquals(new Integer[]{3, 4, 5}, sort(new Integer[]{5, 4, 3}));
Assert.assertArrayEquals(new Integer[]{3, 4, 5}, sort(new Integer[]{5, 3, 4}));
Assert.assertArrayEquals(new Integer[]{3, 4, 5}, sort(new Integer[]{3, 5, 4}));
}
Running this is just as easy as running a main method. This approach also encourages decomposing your problems to elementary operations. In this case I had to extract the sorting logic to its own method to be easier to test. In the end, you will naturally have multiple methods, which is a good thing, at virtually no extra cost.