Peggir
« Blogs
Insertion sort introduced - With Java and Kotlin examples

Insertion sort introduced - With Java and Kotlin examples

2020-11-03 18:57:25.05822

1. Introduction

Insertion sort is an algorithm used for sorting. For example, sorting a list of number or a deck of cards. In this blog post we'll briefly explain how insertion sort works and give a couple of implementations in Kotlin and Java.

2. Background

As you will learn from the explanation in the next chapter, insertion sort is a fairly basic algorithm. Many people that sort a hand of cards, probably do this using insertion sort without realizing it. Because of this, we don't exactly know how old this algorithm is, but we can say that it has been around for a long time. The advantage of insertion sort is that it is a stable sorting algorithm. However, as we will explain in the last chapter, it is not efficient to use on large data sets.

3. How it works

Say we want to sort the following array of numbers (the numbers above the values are the index numbers, A[2] = 6):

Given array of integers

Since we are going to sort our array in place, we will introduce the pointer j. We will initially point j to index 0. The greyed-out part is the sorted subset of A. Because j = 0, we don't have to sort anything.

Pointing j to the first element of A

Let's move on to the next number. We increase j by one: j = 1. Now we have to compare A[j] to its preceding element A[j - 1]. Since A[j] = 3 is smaller than A[j - 1] = 8, we are going to swap their values.

Increasing j and determining whether to swap
Result after swapping 3 and 8

Now we continue to the next element, we increase j to 2. Since A[j] = 6 is lesser than A[j - 1], we are going to swap them. After swapping, we have to continue checking whether 6 is greater or smaller than its preceding elements. Because 6 is greater than 3, we don't have to swap anymore.

Increasing j to 2
Result after swapping 6 and 8

And finally, we move over to our last element in A. Since A[j] = 1 is smaller than any other element in A, we can keep swapping it to the left until it's at the start.

Increasing j to 3
Result after swapping 1 all the way to the left

4. Kotlin implementation

The following Kotlin implementation sorts the given array in place using insertion sort (available on GitHub):


fun main() {
    val input = intArrayOf(8, 3, 6, 1, 9, 20, 0)
    val output = insertionSort(input)
    println(output.contentToString())
}

fun insertionSort(input: IntArray): IntArray {
    for (j in 1 until input.size) {
        val key = input[j]
        var i = j - 1

        while (i >= 0 && input[i] > key) {
            input[i + 1] = input[i]
            i--
        }

        input[i + 1] = key
    }

    return input
}

On line 2 we have our unsorted array of integers that we'd like to sort. Lines 7-21 contains our insertion sort implementation. Line 8 starts our outer loop, that loops through all input array entries (note that it skips the first element). Then, on line 12, we compare whether the picked element from the outer loop needs to be swapped to the left.

5. Java implementation

For our Java implementation (GitHub), we don't sort integers, but Person objects by their age. We made Person implement Comparable, so we can add a compareTo function, that determines whether a person is older, younger or the same age as another person:


public class Person implements Comparable<Person> {

    private final String name;
    private final int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int compareTo(final Person o) {
        if (age > o.getAge()) {
            return 1;
        } else if (age < o.getAge()) {
            return -1;
        }

        return 0;
    }

    public int getAge() {
        return age;
    }

    public String toString() {
        return name + " (" + age + ")";
    }
}

Then, in our App class, we create a list of Person and print the outcome after insertion sorting them:


public class App {

    public static void main(final String[] args) {
        final Person person0 = new Person("Penny", 8);
        final Person person1 = new Person("Ruby", 3);
        final Person person2 = new Person("Johnny", 6);
        final Person person3 = new Person("Mark", 1);
        final Person person4 = new Person("Larry", 9);
        final Person person5 = new Person("Karen", 20);
        final Person person6 = new Person("Cecelia", 0);

        final List<Person> people = new ArrayList<>();
        people.add(person0);
        people.add(person1);
        people.add(person2);
        people.add(person3);
        people.add(person4);
        people.add(person5);
        people.add(person6);

        final List<Person> sortedPeople = insertionSort(people);
        System.out.println(sortedPeople);
    }

    public static List<Person> insertionSort(final List<Person> list) {
        for (int j = 1; j < list.size(); j++) {
            final Person k = list.get(j);
            int i = j - 1;

            while (i >= 0 && list.get(i).compareTo(k) > 0) {
                list.set(i + 1, list.get(i));
                i--;
            }

            list.set(i + 1, k);
        }

        return list;
    }
}

Between lines 4 and 19 we create our list of Person that we'd like to sort. On line 25 we define our insertionSort method. Line 26 starts the outer for-loop that loops over all entries of the input list. Then, again, for each of these entries we have a while-loop (line 30) that swaps items to the left, if needed. You see that is it quite similar as the Kotlin implementation.

6. Efficiency

The running time of insertion sort is O(n2). In the best-case scenario, in which the input already is sorted, it is O(n). If you have taken a look at the code implementations, you would have seen an outer and inner loop, this causes the complexity to be quadratic. Because of this, it is not recommended to use insertion sort on large data sets. However, on (relatively) small data sets, it is a good option.

This concludes the short introduction to insertion sort. If you want to learn more about this algorithm, we recommend you dive deeper into the proof and correctness of the algorithm. That way you'll understand the algorithm even more. All code provided in this blog post are available on GitHub.