digitalmars.D.bugs - [Issue 8331] New: Problem with sort!(SwapStrategy.stable)
- d-bugmail puremagic.com (125/125) Jul 01 2012 http://d.puremagic.com/issues/show_bug.cgi?id=8331
- d-bugmail puremagic.com (19/19) Jul 01 2012 http://d.puremagic.com/issues/show_bug.cgi?id=8331
- d-bugmail puremagic.com (12/12) Feb 24 2013 http://d.puremagic.com/issues/show_bug.cgi?id=8331
- d-bugmail puremagic.com (12/15) Feb 24 2013 http://d.puremagic.com/issues/show_bug.cgi?id=8331
- d-bugmail puremagic.com (8/8) Feb 24 2013 http://d.puremagic.com/issues/show_bug.cgi?id=8331
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
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
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
http://d.puremagic.com/issues/show_bug.cgi?id=8331 bearophile_hugs eml.cc changed: What |Removed |Added ---------------------------------------------------------------------------- Status|NEW |RESOLVED Resolution| |FIXEDPreviously, 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
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