On Saturday, 6 February 2016 at 00:59:17 UTC, Andrei Alexandrescu
wrote:
On 02/05/2016 06:36 AM, Ivan Kazmenko wrote:
Another interesting task would be to make the function stable,
but I don't see how it is possible with such flat structure.
Under what circumstances isn't your function unstable? -- Andrei
For example, if elements are "value | id", compared by value,
then:
0|0, 0|1, 1|2, 0|3, 0|4
is transformed into
0|0, 0|1, 0|4, 0|3, 1|2
and 0|4 is now placed earlier than 0|3, which violates the
stability requirement.
Things can be reordered a bit, but it seems that no possible
order eliminates the need to remember a part of the history.
On the other hand, when we track our whole path in the decision
tree (e.g. at the leaves of Timon Gehr's tree of ifs), we have
all information to make the partition stable.
In any case, finding the shortest-code stable partition-of-5
algorithm looks like a problem solvable by an automated searcher.
Regarding the speed, there are different use cases with different
requirements, for example:
1. Primitive types (cheap swap, cheap comparison).
2. Heavy structs A (expensive swap, cheap comparison - e.g.,
compare one field of primitive type).
3. Heavy structs B (expensive swap, expensive comparison - e.g.,
call a heavy external function).
4. Heavy classes (cheap swap - pointers only, expensive
comparison).
So there's perhaps no single best solution.
