# Use of Sort with custom functions

As mentionned in the topic title, I try to apply my own sorting functions to a set of elements via the Sort command. I make here a quick presentation of the subject before.

1) Method

We will remain in 2D throughout the description of the problem

1-1) Treatment of the component

We consider a component of a vector as a real number.
To sort two real, it is necessary to compare them.
The particularity of the sort that I want to apply is that the comparison depend of a specific criterion c which can take two values ("max" and "min").

In this case, to qualify the order relation between the two numbers, we won't say that :
- something1 is superior/inferior to something2 but,
- something1 dominate/don't dominate something2.

You can either :
- Wanting to maximize the value of the component. c = "max"
- Wanting to minimize the value of the component. c = "min"

Example :

With :

Group n°1 : a1 = 5 and a2 = 3
Group n°2 : a3 = -2 and a4 = -3

• If c = "max"
We have a1 > a2, so a1 dominates a2.
We have a3 > a4, so a1 dominates a2.

• If c = "min"
We always have a1 > a2, but now a2 dominates a1.
We always have a3 > a4, but now a1 dominates a2.

Remarks :
- We can not decide in case of equality, so no number dominates another.
- The criterion c allows you to change the sort direction.

1-2) Treatment of the vector

The functions that I want to use, are based on the principle of dominance (translated from french), and its variations.

Principle 1 :
We say that a vector J dominates a vector K if :
- J is at least as good as K in all component.
- J is strictly better than K in at least one component.

Examples :

Take two vector such as :

v1 = {2, 5};
v2 = {1, 6};

We have several possibilities to compare this two vector according to the value of the criterion c for each of these components.

• v1[[1]] > v2[[1]]
• v1[[2]] < v2[[2]]

Case 1 : {"max","max"}
We can't say if a vector dominate an other.

Case 2 : {"max","min"}
v1 dominate v2.

Case 3 : {"min","max"}
v2 dominate v1.

Case 4 : {"min","min"}
We can't say if a vector dominate an other.

So we can see here, that the sort of this two vector depend directly of the value of c.

2) My code

CompO[w_, x_, y_] :=
Block[
{Res},
Res = If[
x == y,
{0},
If[w == "max", Ordering[{x, y}, -1], Ordering[{x, y}, 1]]]
];

BoolCompVDS[w__, x__, y__] :=
Block[
{step1, step2, step3, Res},
step1 = MapThread[CompO, {w, x, y}];
step2 = DeleteCases[Union@step1, 0, Infinity];
step3 =
If[
Count[step2, _Integer, Infinity] == 1,
Flatten@step2,
{0}
];
Res = If[step3 == {1}, True, False]
];


To understand :

We need to compare two vector :

v1 = {2, 5};
v2 = {1, 6};


The rule (for this example) are the following :
- We want to maximize the first component.
- We want to minimize the second component.

According to the principle 1 :

• v1[[1]] > v2[[1]] so v1[[1]] dominate v2[[1]] (we want to maximize)
• v1[[2]] < v2[[2]] so v1[[2]] dominate v2[[2]] (we want to minimize)

So v1 dominate v2 and :

BoolCompVDS[{"max","min"}, v1, v2]


give "True"

3) Problem

Thanks to the post of Mr. Wizards, my original question can be formulated like this :
Why the use of Sort with my personal function does not produce a strict order as may be the case with the use of the Norm function (for example) ?

As seen in the post of Mr Wizards, the Sort command is designed to work with strict order relations.
I would write an answer for an update on sorting with function based on dominance relations soon.

• Please explain what do you exactly mean by "If the sort function BoolCompVDL Work, this is not the case with the functions BoolCompVDS and BoolCompVDM." (in which way/s they don't "work") – Dr. belisarius Feb 17 '16 at 10:38
• Agree "that's a lot of information to integrate", a more minimalistic question would be easier to answer. – rhermans Feb 17 '16 at 11:22
• You are giving too much irrelevant information. This is a serious mental load on all those who would try to answer. My first reaction is to ignore the question, and I am sure I am not alone. Look at some of the reasonably voted questions for examples of how to formulate a question well, and construct a minimal example, if you want to increase the chances for good answers. – Leonid Shifrin Feb 17 '16 at 13:01
• Could you specify a general rule, how two vectors {a, b} and {c, d} should be ordered? I find part 2 of your question incredibly hard to comprehend. As I think I have gathered, the ordering {{a, b}, {c, d}} is correct if a < c and b > d, but for the example functions #^2 and #^3 this is never simultaneously realized. – LLlAMnYP Feb 17 '16 at 13:12
• Why is BoolCompVDS defined with three parameters of variable length i.e. BoolCompVDS[w__, x__, y__] and what do you expect this to do? – Mr.Wizard Feb 17 '16 at 17:40

### Establishing the question

Working through this post was confusing but I think I at least understand your question now.

First let me see if I can reduce your code quite a lot. :-) I believe your BoolCompVDS can be replaced with merely this:

fn1[c_][v1_, v2_] := Min[#] >= 0 && Max[#] > 0 &[(v1 - v2) c]


The c parameter takes a list of 1 or -1 representing "max" or "min" respectively.

There is equivalence:

rnd = RandomReal[{-9, 9}, {100, 2, 2}];

Equal[
BoolCompVDS[{"max", "max"}, #1, #2] & @@@ rnd,
fn1[{1, 1}] @@@ rnd
]

True


Now the question is why the final output of this is not all True:

{{-2, -2}, {1, -4}, {1, 0}, {-1, -4}, {-3, 1}};
Sort[%, fn1[{1, 1}]]
Partition[%, 2, 1]
fn1[{1, 1}] @@@ %

{{-3, 1}, {1, 0}, {1, -4}, {-1, -4}, {-2, -2}}

{{{-3, 1}, {1, 0}}, {{1, 0}, {1, -4}}, {{1, -4}, {-1, -4}}, {{-1, -4}, {-2, -2}}}

{False, True, True, False}


Is my understanding correct?

### Examining the situation

I believe Sort operates assuming that the ordering function produces a strict order, meaning among other things that a < b and b < c implies a < c, and I believe your ordering function does not conform to this requirement. Here is a simpler example of the issue:

fn = Mod[#, 2] < Mod[#2, 3] &;

Sort[Range @ 10, fn]

fn @@@ Partition[%, 2, 1]

{9, 6, 7, 1, 2, 4, 3, 5, 8, 10}

{False, True, False, True, True, False, True, True, True}


I recall that there are ways to work with this kind of ordering though I cannot recall the details. I think in any case the problem requires additional specification. Some references that may help with that:

• Min[#] >= 0 && Max[#] > 0 & - if the smallest of two quantities is positive, no need to test if the larger quantity is also positive, no? – J. M.'s ennui Feb 17 '16 at 19:23
• @J.M. The minimum needs to be zero-or-greater, while the maximum must be strictly greater-than-zero. This is by my understanding of the OP's Principle 1 and it appears to agree with his own function. I suppose another way to write this would be NonNegative @ Min[#] && Max[#] != 0. – Mr.Wizard Feb 17 '16 at 19:39
• What I had in mind was something like Min[#] > 0 || Min[#] < Max[#], so that it short-circuits as soon as it is known that the minimum is positive. – J. M.'s ennui Feb 17 '16 at 19:46
• @J.M. That didn't occur to me. :-) – Mr.Wizard Feb 17 '16 at 20:24
• @Mr.Wizard. Based on your results, you understood everything. – Doedalos Feb 18 '16 at 14:15

I make here a rapid conclusion on the various sorting methods that I want to study.

The different elements to understand the problem and presented in the first post still valid.

Here you can see the various principles that I wanted to implement and the associated code.

Principle

• Principle 1 :
We say that a vector J dominates a vector K if :
-J is at least as good as K in all component.
-J is strictly better than K in at least one component.

• Principle 2 :
We say that a vector J dominates a vector K if :
-If the value of the worst component of J is smaller than the worst component of K.

• Principle 3 :
We say that a vector J dominates a vector K if :
-There is an index value q such as all the components between 0 and q (included) are equal.
-The component of J at the position (q + 1) dominates the component of K on the same position.

Here you can see the corresponding code :

CompO[w_, x_, y_] :=
Block[
{Res},
Res = If[
x == y,
{0},
If[w == "max", Ordering[{x, y}, -1], Ordering[{x, y},1]]
]
];

BoolCompVDS[w__, x__, y__] :=
Block[
{step1, step2, step3, Res},
step1 = MapThread[CompO, {w, x, y}];
step2 = DeleteCases[Union@step1, 0, Infinity];
step3 =
If[
Count[step2, _Integer, Infinity] == 1,
Flatten@step2,
{0}
];
Res = If[step3 == {1}, True, False]
];

BoolCompVDM[w__, x__, y__] :=
Block[
{step0, step1, step2, step3, step4, Res},
step0 = {x, y};
step1 = MapThread[CompO, {w, x, y}];
step2 = (Flatten@step1) /. {1 -> 2, 2 -> 1};
step3 = Ordering[Abs@Table[step0[[i, step2[[i]]]], {i, 1, 2, 1}], -1];
step4 = (step2[[step3]]) /. {1 -> 2, 2 -> 1};
Res = If[step4 == {1}, True, False]
];

BoolCompVDL[w__, x__, y__] :=
Block[
{step1, step2, step3, Res},
step1 = Flatten@MapThread[CompO, {w, x, y}];
step2 = FirstPosition[step1, 1 | 2, {0}];
step3 = If[step2[[1]] != 0, step1[[step2]], {0}];
Res = If[step3 == {1}, True, False]
];

SortVDS[x_, y_] := Sort[x, BoolCompVDS[y, #1, #2] &];
SortVDM[x_, y_] := Sort[x, BoolCompVDM[y, #1, #2] &];
SortVDL[x_, y_] := Sort[x, BoolCompVDL[y, #1, #2] &];


To compare the results of different sort :

data = RandomInteger[{-9, 9}, {10, 2}];

SortVDS[data, {"max", "max"}]
SortVDM[data, {"max", "max"}]
SortVDL[data, {"max", "max"}]


We obtain :

Random list >> {{2, -5}, {-6, 5}, {6, 9}, {-6, -4}, {4, -6}}

Sort n°1 >> {{6, 9}, {4, -6}, {-6, 5}, {-6, -4}, {2, -5}}
Sort n°2 >> {{6, 9}, {-6, -4}, {-6, 5}, {2, -5}, {4, -6}}
Sort n°3 >> {{6, 9}, {4, -6}, {2, -5}, {-6, 5}, {-6, -4}}

As mentioned by Mr.Wizards, only the principle 3 allows a total ordering.
This does not mean that the other sort are uninteresting.