💡 105. Pancake sort in Raku

The Pancake sort is an interesting method of sorting data, as unlike more traditional sorting algorithms, it operates with piles of data on each step.

You have to imagine data as a pile of pancakes, the values corresponding to the size of pancakes. The only allowed operation is flipping a pile of ‘pancakes.’ It can be any number of them, but they can be only the ones on the top of the whole pile.

You start from bottom and go one step up on each iteration. In the upper part of the pile, you search for the biggest pancake, and flip the pile from that position (thus, rotate the whole upper part including the just found maximum value). Then you rotate the top pile from the top to and including the pancake corresponding to the current step counter. Repeat until ready.

While it may sound weird, the algorithm really works. Let us implement it using approaches available in a generic programming language.

sub pancake-sort(@data) {
    my $n = @data.elems - 1;

    while $n > 1 {
        my $m = $n;
        my $max_n = $m;
        my $max = @data[$m];
        while --$m {
            if @data[$m] > $max {
                $max = @data[$m];
                $max_n = $m;
            }
        }

        @data[0..$max_n] .= reverse;
        @data[0..$n] .= reverse;
        
        $n--;
    }
}

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

The two flips are clearly seen: those are the two .=reverse calls.

A big part of code is about searching for the maximum value on the current iteration. In Perl 6, there is the max routine, but we cannot directly use it as we need to find the position of the maximum element, not the element itself.

Perl 6 has a answer for that task too! It is the maxpairs method, which returns a sequence (an object of the Seq class) containing the pairs for all maximum elements: the key of a pair is the index of the element.

An updated version of the code is much shorter. It immediately uses the result of maxpairs in place of the $max_n value.

sub pancake-sort(@data) {
    my $n = @data.elems - 1;

    while $n > 1 {
        @data[0 .. @data[0..$n].maxpairs[*-1].key] .= reverse;
        @data[0..$n] .= reverse;
        
        $n--;
    }
}

Another possibility for making the code even more beautiful is to get rid of explicit counters in the while loop. As the counter goes down, ranges will not help: 10..1 produces Nil. But sequences can do that: 10...1 contains ten numbers. Let’s embed it to the sorting function:

sub pancake-sort(@data) {
    {
        @data[0 .. @data[0..$_].maxpairs[*-1].key] .= reverse;
        @data[0 .. $_] .= reverse;
    } for @data.elems - 1 ... 1;
}

This is where you can stop: the code is simple, clean and transparent. Or even yummy! Take a pancake on GitHub and add your flavour!