💡 106. Gnome sort in Raku

Our today’s topic is the Gnome sort, which is also referred to as Stupid sort. To sort an array using this method, you scan the data from left to right and check the two adjacent items to see if they are ordered properly. If they are, you go forward. If not, you swap the elements and make a step back.

Here is the first implementation based on the above description:

sub gnome-sort(@data) {
    my $pos = 0;

    while $pos != @data.elems - 1 {
        if !$pos or @data[$pos] >= @data[$pos - 1] {
            $pos++;
        }
        else {
            @data[$pos, $pos - 1] .= reverse;
            $pos--;
        }
    }
}

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

If you would follow the $pos value, you could see the long path that the gnome walked along the data to sort it:

0, 1, 2, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1, 2, 3, 4, 5, 6, 7, 6, 5, 4, 3, 2, 3, 4, 5, 6, 7, 8, 7, 6, 5, 4, 3, 2, 1, 2, 3, 4, 5, 6, 7, 8, 9, 8, 7, 8, 9, 10, 9, 8, 9, 10

The path above looks like some sequence, and it can be a good idea to use the Seq class available in Perl 6. Let me remind that you can generate sequences with the ... operator equipped with your own block of code to compute the next value. The interesting things is that you can also call an external function from that generator code block.

I am moving the main logic to a sub-function and here’s the code:

sub gnome-sort(@data) {

    sub f($i) {
        return 1 unless $i;

        if @data[$i] >= @data[$i - 1] {
            return $i + 1;
        }
        else {
            @data[$i, $i - 1] .= reverse;
            return $i - 1;
        }
    }

    for 1, -> $i {f($i)} ... @data.elems {
        
    }
}

As you see, the sequence is only needed to generate, erm, the sequence. The body of the loop is empty, as all the job is done within f.

Now, we can clean the code a bit and remove the unnecessary punctuation:

sub gnome-sort(@data) {

    sub f($i) {
        return 1 unless $i;
        return $i + 1 if [>=] @data[$i, $i - 1];
        
        @data[$i, $i - 1] .= reverse;
        return $i - 1;
    }

    1, -> $i {f($i)} ... @data.elems;
}

You may notice that the for loop is also gone, and the sequence is left alone. This is probably not a good practice as Perl could potentially optimise it and generate a lazy sequence instead. But it works as of today.

What you also can do is to split the function into three multi-functions, and make the whole code look very functional-programming-oriented.

sub gnome-sort(@data) {

    multi sub f(0) { 1 }

    multi sub f($i where [>=] @data[$i, $i - 1]) { $i + 1 }

    multi sub f($i) {
        @data[$i, $i - 1] .= reverse;
        return $i - 1;
    }

    1, -> $i {f($i)} ... @data.elems;
}

An update based on the comments left by a reader on Reddit. It is possible to further simplify the sequence by passing f as a callable object:

sub gnome-sort(@data) {

    proto sub f($) { * } 

    . . . # all multi-subs here

    1, &f ... @data.elems;
}

Nevertheless, it’s all for today. Check the code on GitHub and suggest any changes if you think they may be interesting for the readers.