4
\$\begingroup\$

I have implemented Insertion sort in Java. Please review it.

public class InsertionSort {

public static void main(String[] args) {
        int[] values = new int[args.length];
        for (int i = 0; i < args.length; i++) {
            values[i] = Integer.parseInt(args[i]);
        }

        for (int i = 0; i < values.length; i++) {
            if (i!=0 && values[i] < values[i - 1]) {
                for (int j = i; j >= 1; j--) {
                    System.out.println(" j"+j);
                    if (values[j] < values[j-1]) {
                        int temp = values[j - 1];
                        values[j - 1] = values[j];
                        values[j] = temp;
                    } else {
                        break;
                    }
                }
            }
        }
        System.out.println(" sorted numbers");
        for (int i = 0; i < values.length; i++) {
            System.out.println(" "+values[i]);
        }
    }
}
\$\endgroup\$

1 Answer 1

7
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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