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: nob...@puremagic.com ReportedBy: bearophile_h...@eml.cc --- Comment #0 from bearophile_h...@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@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: -------