www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 8331] New: Problem with sort!(SwapStrategy.stable)

reply d-bugmail puremagic.com writes:
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 puremagic.com
        ReportedBy: bearophile_hugs eml.cc



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 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: -------
Jul 01 2012
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8331




This little Python program gives the same output as the merge sort and
insertion sort (Python built-in sort is stable):


from itertools import imap
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]
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]

def cmp(i, j):
    if b[i] * a[j] > b[j] * a[i]: return -1
    elif b[i] * a[j] < b[j] * a[i]: return 1
    return 0

print sorted(range(len(a)), cmp=cmp)


Outputs:
[11, 19, 22, 1, 4, 3, 24, 10, 18, 8, 17, 23, 20, 7, 5, 12, 15, 0, 13, 9, 6, 16,
21, 14, 2, 25]

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 01 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8331


Xinok <xinok live.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |xinok live.com



Previously, the stable sort in Phobos was broken which may be why this code
failed. It has since been fixed, so if that was indeed the problem, we can
probably close this bug report.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 24 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8331


bearophile_hugs eml.cc changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED





 Previously, the stable sort in Phobos was broken which may be why this code
 failed. It has since been fixed, so if that was indeed the problem, we can
 probably close this bug report.


Right, thank you. Closed.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 24 2013
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8331


bearophile_hugs eml.cc changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|FIXED                       |WORKSFORME


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