💡 107. Odd-even sort in Raku

In the Odd-Even sort, or Brick sort, you take every second element and swap it with the next one if they are not sorted. Then you take the same elements and swap it with the previous element if they are not ordered. You continue until you are done.

You can formulate the algorithm a bit differently, and then you will clearly have odd and even elements: first, you compare odd elements with its neighbours, then you compare even elements. If you draw the working pairs on each step, you will see the shape resembling the layout of a brick wall.

In the first approach, let’s duplicate the code for each stage: odd and even.

sub odd-even-sort(@data) {
    my $done = False;
    while !$done {
        $done = True;
        loop (my $i = 0; $i < @data - 1; $i += 2) {
            if [>] @data[$i, $i + 1] {
                $done = False;
                @data[$i, $i + 1].=reverse;
            }
        }
        loop ($i = 1; $i < @data; $i += 2) {
            if [>] @data[$i, $i + 1] {
                $done = False;
                @data[$i, $i + 1].=reverse;
            }
        }
    }
}

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

There are two C-style loops here, both with the step 2.

It is possible to simply repeat the procedure @data.elems times, so you can remove the $done flag and use the postfix ifs.

sub odd-even-sort(@data) {
    for ^@data {
        loop (my $i = 0; $i < @data - 1; $i += 2) {
            @data[$i, $i + 1].=reverse if [>] @data[$i, $i + 1];
        }
        loop ($i = 1; $i < @data; $i += 2) {
            @data[$i, $i + 1].=reverse if [>] @data[$i, $i + 1];
        }
    }
}

Actually, if you want to use a flag, you can still do it with postfix if conditions:

sub odd-even-sort(@data) {
    my $done = False;
    while !$done {
        $done = True;
        loop (my $i = 0; $i < @data - 1; $i += 2) {
            $done--, @data[$i, $i + 1].=reverse 
                if [>] @data[$i, $i + 1];
        }
        loop ($i = 1; $i < @data; $i += 2) {
            $done--, @data[$i, $i + 1].=reverse
                if [>] @data[$i, $i + 1];
        }
    }
}

But that was the minor thing (although it is important for performance). For code beauty, we need to merge the loops, as they do the same work, just for different pairs of elements.

What if another loop with two iterations?

sub odd-even-sort(@data) {
    my $done = False;
    while !$done {
        $done = True;
        for 0..1 -> $start {
            loop (my $i = $start; $i < @data - 1 - $start; $i += 2) {
                $done--, @data[$i, $i + 1].=reverse 
                    if [>] @data[$i, $i + 1];
            }
        }
    }
}

Not bad, but what about sequences? Let us make a very verbose but quite understandable list of values that consists of two parts: even and odd indices:

sub odd-even-sort(@data) {
    my $done = False;
    while !$done {
        $done = True;
        for flat(
                (0, 2 ... @data - 2), (1, 3 ... @data - 1)
            ) -> $i {
            $done--, @data[$i, $i + 1].=reverse 
                if [>] @data[$i, $i + 1];
        }
    }
}

Of course, the for loop can go to the postfix part:

sub odd-even-sort(@data) {
    my $done = False;
    repeat {
        $done = True;
        $done--, @data[$_, $_ + 1].=reverse
            if [>] @data[$_, $_ + 1]
            for flat((0, 2 ... @data - 2), (1, 3 ... @data - 1));
    } until $done;
}

Or, if you don’t like using a flag:

sub odd-even-sort(@data) {
    while ![<=] @data {
        @data[$_, $_ + 1].=reverse if [>] @data[$_, $_ + 1]
            for flat((0, 2 ... @data - 2), (1, 3 ... @data - 1));
    }
}

(An extra comparison step can significantly slow the algorithm down.)

At this point, the code is quite compact, and if you’d like to work on it further, you have to express the sequence of odd and event numbers with less characters of code.

I wish you success! If you succeed, please share the solution with us. The source codes of all versions are available on GitHub.