In-Place Insertion Sort

Question

Purpose

Implementation for in-place Insertion Sort.

Discussion

The idea is to start with the second element in the input array (in the single element case, it's already sorted).

Moving backwards, compare the value against each prior element in the array until

1. You reach the beginning of the array
2. You find an element that is <= your value

As you continue backwards, move the last value you considered to the next index in the array.

Then repeat the same steps for the third, fourth, etc. elements, if they exist.

Implementation

public class InsertionSorter {
    public static void sort(int[] values) {
        for (int index = 1; index < values.length; index++) {
            int value = values[index];
            int nextIndex = index - 1;
            while (nextIndex >= 0 && values[nextIndex] > value) {
                values[nextIndex + 1] = values[nextIndex];
                nextIndex--;
            }
            values[nextIndex + 1] = value;
        }
    }
}

Answer 1

Naming index and nextIndex as i and j would have been OK.

There are no comments, which is not necessarily a problem. But a one-line javadoc for the function would be helpful. I know, I know, from the signature it's kind of obvious, but still. For example, what if caller passes in null? Well, we throw a fatal exception, and that seems appropriate, caller gets what he deserves, he violated the contract spelled out in the javadoc. But only if there is a javadoc explaining the caller's responsibility.

The inner while loop would be more naturally expressed as a for loop.

The inner while loop might become a helper function. Then you'd have the opportunity to give it an informative name, perhaps copy.

That said, overall the function as written is reasonably clear.

Answer 2

Hi thanks for sharing your code!

My answer isn't going to touch on the algorithm itself, but I wanted to talk about a way that you could make your insertion sorter more flexible.

At the moment, your sorting only handles integers, if you were to use generics that implement Comparable your insertion sort anything that implements that interface.

Consider the following classes ( your algorithm remains unchanged)

Sorter interface

public interface Sorter<T extends Comparable<T>> {
    T[] sort();
}

This Sorter interface at the moment has just one implementation, but if you decided to work on other sorting algorithms, you could make a MergeSorter, QuickSorter, TimSorter etc.

I've changed from a static method to an object that you instantiate.

Insertion Sorter Class

    public class InsertionSorter<T extends Comparable<T>> implements Sorter<T> {

        private final T[] values;

        public InsertionSorter(T[] values) {
            this.values = values;
        }

        @Override
        public T[] sort() {
            for (int index = 1; index < values.length; index++) {
                T value = values[index];
                int nextIndex = index - 1;
                while (nextIndex >= 0 && values[nextIndex].compareTo(value) >= 0) {
                    values[nextIndex + 1] = values[nextIndex];
                    nextIndex--;
                }
                values[nextIndex + 1] = value;
            }
            return values;
        }
    }

Main

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        String[] stringArr = new String[]{"b", "c", "a", "g", "k"};
        Sorter<String> stringInsertionSorter = new InsertionSorter<>(stringArr);
        System.out.println(Arrays.toString(stringInsertionSorter.sort()));

        Integer[] intArr = new Integer[]{1, 7, 5, 3, 4, 5};
        Sorter<Integer> intInsertionSorter = new InsertionSorter<>(intArr);
        System.out.println(Arrays.toString(intInsertionSorter.sort()));
    }
}

here's the output of this program.

[a, b, c, g, k] [1, 3, 4, 5, 5, 7]

And as I mentioned before, you could write some code that looks something like this.

Sorter<SomethingComparable> mergeSorter = new MergeSorter<>(arr);
mergeSorter.sort();

At the moment this code will mutate the existing array, so you may want to create a copy instead.

Hopefully you found some of this useful!