๐Ÿ’ก 102. Insertion sort in Perl 6

Today, we are investigating the Insertion sort algorithm and its possible implementation in Perl 6. The algorithmโ€™s complexity is O(n2), 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.

4 thoughts on “๐Ÿ’ก 102. Insertion sort in Perl 6”

  1. Note that splice() itself is of course not constant in time complexity, which can be seen from this (underwhelmingly erratic and simplistic) test:

    for (4,4,4..10).flat -> $n {
    my @array = ‘a’ xx (10 ** $n);
    my $stride = ((10 ** $n) / 500).Int;
    my $start = now;
    for 0..499 -> $x {
    @array.splice($stride * $x, 0, ‘b’);
    }
    my $duration = now – $start;
    say “{sprintf(“%10i”, 10 ** $n)}: {sprintf(“%.7f”, $duration.Real / 500)}”;
    }

    which gave me this until I ran out of patience:
    10000: 0.0000199
    10000: 0.0000271
    10000: 0.0000046
    100000: 0.0000139
    1000000: 0.0001177
    10000000: 0.0117490
    100000000: 0.0741589

    Like

  2. > 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.

    That statement sounds confusing to me. Correct me if I am wrong, but the mentioned code:

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

    Does the opposite, it finds the first element in _array_ which is greater then current element iterated in the first loop, does not it?

    Like

  3. For a given value $N of @data at index $i, .first iterates through @data’s elements until the first time that the current element (represented by *) is larger than $N – or, the first time $N is less than *, same thing. (I’m leaving out the “or equals” for brevity.) If that’s how you see it, you are right. Here’s how I untangle the code to show that you are right AND the code is correct:

    So again, using $N as @data[$i], .first iterates through @data’s elements until the first time that the current element (represented by *) is larger than $N. The index of .first’s current element is returned, becoming the first argument to the outer splice – telling the outer splice where to put what will be spliced in. The element to be spliced in is $N, provided as the third argument to the outer splice by being extracted by the inner splice from its original position $i in @data. $N is now where that last value repped by * was, and that * value is one index position further from the start of @data.

    That code
    @data.first(* >= @data[$i], :k), # first time * is larger than/equal to @data[$i]
    could have been written as
    @data.first(@data[$i] <= *, :k), # first time @data[$i] is less then/equal to *
    to look more parallel to the written description.

    HTH

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s