[Issue 8331] New: Problem with sort!(SwapStrategy.stable)

[d-bugmail at puremagic.com]

http://d.puremagic.com/issues/show_bug.cgi?id=8331

           Summary: Problem with sort!(SwapStrategy.stable)
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Phobos
        AssignedTo: nobody at puremagic.com
        ReportedBy: bearophile_hugs at eml.cc


--- Comment #0 from bearophile_hugs at eml.cc 2012-07-01 08:59:04 PDT ---
In this program I have used sort!(SwapStrategy.stable) on a small amount of
data, and I have compared its results with two very different stable sorts (an
insertion sort and a merge sort). The insertion sort and the merge sort give
the same results, but their result is different from
sort!(SwapStrategy.stable):


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

enum a =
[45,8,94,23,30,61,99,48,49,92,32,1,71,45,6,65,54,34,37,7,64,80,9,23,33,30];

enum b =
[45,55,38,66,89,82,92,70,92,86,63,25,95,45,3,84,42,58,70,83,98,53,72,36,88,0];

static assert(a.length == b.length);

bool myLess(in int i, in int j) pure nothrow {
    return b[i] * a[j] > b[j] * a[i];
}

void insertionSort(T)(T[] data) pure nothrow {
    foreach (i, value; data[1 .. $]) {
        auto j = i + 1;
        for ( ; j > 0 && myLess(value, data[j - 1]); j--)
            data[j] = data[j - 1];
        data[j] = value;
    }
}


void merge_sort(int[] list2) pure nothrow {
    // merge (used by merge_sort_r)
    static void merge(int[] list2, in int first, in int last, in int sred) pure
nothrow {
        int[] helper_list;
        int i = first;
        int j = sred + 1;
        while (i <= sred && j <= last) {
            if (myLess(list2[i], list2[j])) {
                helper_list ~= list2[i];
                i++;
            } else {
                helper_list ~= list2[j];
                j++;
            }
        }
        while (i <= sred) {
            helper_list ~= list2[i];
            i++;
        }
        while (j <= last) {
            helper_list ~= list2[j];
            j++;
        }
        foreach (k; 0 .. last - first + 1)
            list2[first + k] = helper_list[k];
    }

    // merge sort recursive (used by merge_sort)
    static void merge_sort_r(int[] list2, in int first, in int last) pure
nothrow {
        if (first < last) {
            const sred = (first + last) / 2;
            merge_sort_r(list2, first, sred);
            merge_sort_r(list2, sred + 1, last);
            merge(list2, first, last, sred);
        }
    }

    merge_sort_r(list2, 0, list2.length -1);
}

void main() {
    const c = a.length.iota().array();

    auto c1 = c.dup;
    sort!(myLess, SwapStrategy.stable)(c1);
    writeln(c1);

    auto c2 = c.dup;
    insertionSort(c2);
    writeln(c2);

    auto c3 = c.dup;
    insertionSort(c3);
    writeln(c3);

    assert(c2 == c3); // OK
    assert(c1 == c2); // asserts
}

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

With a little more input data sort!(SwapStrategy.stable) gives a "Failed to
sort range":


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

enum a = [22, 45, 8, 94, 23, 30, 61, 99, 48, 49, 92, 32, 1, 71, 45, 6, 65,
54, 34, 37, 7, 64, 80, 9, 23, 33, 30, 19, 30, 97, 40, 42, 7, 7, 52, 5, 35,
50, 92, 14, 17, 8, 72, 23, 33];

enum b = [58, 45, 55, 38, 66, 89, 82, 92, 70, 92, 86, 63, 25, 95, 45, 3,
84, 42, 58, 70, 83, 98, 53, 72, 36, 88, 0, 1, 41, 23, 37, 51, 83, 17, 61,
37, 3, 4, 98, 15, 52, 69, 12, 47, 87];

static assert(a.length == b.length);

bool myLess(in int i, in int j) pure nothrow {
    return b[i] * a[j] > b[j] * a[i];
}

void main() {
    auto c1 = a.length.iota().array();
    c1.sort!(myLess, SwapStrategy.stable)();
    writeln(c1);
}


DMD 2.060alpha:

core.exception.AssertError at C:\dmd2\src\phobos\std\algorithm.d(6993): Failed to
sort range of type uint[]. Actual result is: [12, 20, 32, 41, 23, 35, 2, 40]...
----------------
0x00417520 in char[][] core.sys.windows.stacktrace.StackTrace.trace()
0x004173AB in core.sys.windows.stacktrace.StackTrace
core.sys.windows.stacktrace.StackTrace.__ctor()
0x004026B3 in _Dmain at C:\leonardo\googleCodeJam2012Round3\test3.d(29)
0x0040AD38 in extern (C) int rt.dmain2.main(int, char**).void runMain()
0x0040AD72 in extern (C) int rt.dmain2.main(int, char**).void runAll()
0x0040A994 in main
0x0041F081 in mainCRTStartup
0x777BD309 in BaseThreadInitThunk
0x77631603 in RtlInitializeExceptionChain
0x776315D6 in RtlInitializeExceptionChain

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------