💡 106. Gnome sort in Perl 6

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.

One thought on “💡 106. Gnome sort in Perl 6”

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