bearophile_hugs@eml.cc 
| 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
--- Comment #0 from bearophile_hugs@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: -------
|
Permalink
Reply
