💡 102. Insertion sort in Raku

Today, we are investigating the Insertion sort algorithm and its possible implementation in Perl 6. The algorithm’s complexity is O(n²), but it is a good candidate to practice some Perl 6.

The idea is simple. You find the minimum value in the array and put it to the first position. Then you scan the data starting from the second position (as the first position is already occupied with the lowest element). And you go on to the right, finding minimums and placing them to the current position until you reach the end.

It is similar to Selection sort, but instead of swapping the two elements, you insert one (and thus, shift the others). Let us start with the straightforward approach and two nested loops:

sub insertion-sort(@data) {
    for ^@data -> $i {
        for ^$i -> $j {
            if @data[$i] < @data[$j] {
                @data.splice($j, 0, @data[$i]);
                @data.splice($i + 1, 1);
            }
        }
    }
}

my @data = 4, 5, 7, 1, 46, 78, 2, 2, 1, 9, 10;
insertion-sort @data;
say @data;

In Perl 6, the splice method of arrays can serve two tasks: replace the part of the array with another list of elements or simply remove the element or a few elements in a row.

In the above code, both applications of the method are used. First, the new found element is inserted to the current position. Second, it is removed from its previous place (the array just grew, so the index became $i + 1).

As the splice method also returns the removed element(s), we can put the second call to the place where the element is being read: @data[$i]. And thus the two lines can be replaced with the following nested calls:

@data.splice($j, 0, @data.splice($i, 1))

Notice that the index is simply $i now as the array is not yet modified.

You should be already familiar with the second possible trick: let’s use the postfix if:

sub insertion-sort(@data) {
    for ^@data -> $i {
        for ^$i -> $j {
            @data.splice($j, 0, @data.splice($i, 1)) 
                if @data[$i] < @data[$j];
        }
    }
}

You can stop at this point, but I hope you are not yet satisfied. At least, the two nested fors seem to be a good field for further thinking.

Unfortunately, it is not possible to directly use a cross operator to have something like for ^@data X ^@data, as the second list depends on the first one, but there is a completely different way to simplify the code.

The primary goal of the most inner for loop is to find the first minimum element in the array. Perl 6 gives us the first method, which does exactly that.

By default, it returns the element, but we need its index. You do that by adding the :k named parameter:

@data.first(* >= @data[$_], :k)

A bare :k is equivalent to setting the parameter to True: :k(True) or k => True.

sub insertion-sort(@data) {
    for ^@data -> $i {
        @data.splice(
            @data.first(* >= @data[$i], :k), 
            0,
            @data.splice($i, 1)
        )
    }
}

Finally, make the only remaining for loop a postfix clause, and you are done with a nice one-line function (shown here split into shorter parts on different lines):

sub insertion-sort(@data) {
    @data.splice(
        @data.first(* >= @data[$_], :k), 
        0,
        @data.splice($_, 1)
    ) for ^@data;
}

my @data = 4, 5, 7, 1, 46, 78, 2, 2, 1, 9, 10;
insertion-sort @data;
say @data;

That’s all for now, but if you find something that can be improved, please let us know in the comments below. The source codes are available on GitHub.