Pancake Sort comparison

[bearophile]

Another comparison, a translation of a small Python program to D2+Phobos2.
Again the original program was in the rosettacode site.

The task asks to implement the Pancake sort, with few demo prints in the middle:
http://en.wikipedia.org/wiki/Pancake_sorting

---------------------

The starting Python 2.x version (not written by me, I have just improved few things):


def pancakesort(data, tutor=False):
    if len(data) <= 1:
        return
    for size in xrange(len(data), 1, -1):
        maxindex = max(range(size), key=data.__getitem__)
        if maxindex+1 != size:
            # This indexed max needs moving
            if maxindex != 0:
                # Flip the max item to the left
                if tutor:
                    print "With:", "".join(map(str, data)), "doflip", maxindex+1
                data[:maxindex+1] = data[:maxindex+1][::-1]
            # Flip it into its final position
            if tutor:
                print "With:", "".join(map(str, data)), "doflip", size
            data[:size] = data[:size][::-1]

if __name__ == "__main__":
    import random

    data = list("123456789")
    while data == sorted(data):
        random.shuffle(data)
    print "Original List:", "".join(map(str, data))
    pancakesort(data, tutor=True)
    print "Pancake Sorted List:", "".join(map(str, data))

---------------------

A possible D2+Phobos translation:


import std.stdio, std.algorithm, std.range, std.random;

void pancakeSort(bool tutor=false, T)(T[] data) {
    if (data.length <= 1)
        return;
    foreach_reverse (size; 2 .. data.length + 1) {
        int maxIndex = size - minPos!("a > b")(data[0 .. size]).length;
        if (maxIndex + 1 != size) {
            // This indexed max needs moving
            if (maxIndex != 0) {
                // Flip the max item to the left
                static if (tutor)
                    writeln("With: ", data, " doflip ", maxIndex + 1);
                data[0 .. maxIndex + 1].reverse;
            }
            // Flip it into its final position
            static if (tutor)
                writeln("With: ", data, " doflip ", size);
            data[0 .. size].reverse;
        }
    }
}

void main() {
    char[] data = "123456789".dup;
    while (data == data.dup.sort)
        randomShuffle(data);
    writeln("Original List: ", data);
    pancakeSort!true(data);
    writeln("Pancake Sorted List: ", data);
}


I like the reverse property of the built-in D arrays.

It's probably possible to make this D2 code more general, so it can sort single linked lists too, but it's not worth it and the code gets longer and less easy to understand.

During the translation I have found only two small troubles:

This Python line:
  for size in xrange(len(data), 1, -1):
    
Can't be translated like this:
  foreach (size; iota(data.length, 1, -1)) {
because length is unsigned, so for the way iota() is designed my code was buggy.
That's another example of why I prefer signed array lengths :-)

This works:
  foreach (size; iota(cast(int)data.length, 1, -1)) {

This is another way to translate it that avoids a cast:
  foreach_reverse (size; iota(2, data.length+1)) {

Or just:
  foreach_reverse (size; 2 .. data.length + 1) {


The other small trouble has come from translating this not obvious Python idiom:
        maxindex = max(range(size), key=data.__getitem__)

range(size) is similar to array(iota(size)).

__getitem__ is the standard Python method (of list) that supports the [] operator, similar to opIndex.

In both Python and my dlibs1 the max() takes a second optional argument that is a key mapper function (similar to the function of schwartzSort of Phobos2 (I'd like schwartzSort to be renamed to something simpler to write, I have to look in the docs for its spelling every time I want to use it)), that is quite handy.

So the Python code generates the array of the first size integers, and maps on them the first items of data, finds their max, and then returns the item of the array, that is its index.

In this case Phobos2 offers minPos that is more fitting for the job. But curiously minPos doesn't return an iteger, it returns a range, so if you need the position you need something like:
a.length - minPos(a).length

I presume the way minPos is designed makes it more elastic, but in most cases I don't need the resulting range (I don't know in what situations you need the minPos as currently designed).

In my opinion the current "minPos" name is not good, because this function doesn't return a position, and it's doesn't find just the minimum. The absence of maxPos can be understood, but it needs a bit of adjustment for the programmer, because you can use it to find the max too. In Python there is both the min and max because it accepts the key function, and it's sometimes not easy to invent a key function (think about finding the max or min in an array of strings).

So in the end I have translated it with:
int maxIndex = size - minPos!("a > b")(data[0 .. size]).length;

But in a situation like that (that is common) I prefer to write:
int maxIndex = maxPos(data[0 .. size]);

This time I have found no Phobos2 or D2 bugs :-)

Bye,
bearophile