5
$\begingroup$

Heres an MWE

Sort[{1, 2, .1, 0, -2, 3}, If[#1 > 0, #1 < #2, False] &]

(*{0.1,1,2,3,-2,0}*)

Ordering[{1, 2, .1, 0, -2, 3}, 1, If[#1 > 0, #1 < #2, False] &]

(*{6}*)

Ordering[{1, 2, .1, 0, -2, 3}, 2, If[#1 > 0, #1 < #2, False] &]

(*{3,1}*)

Why is there this behavior? Specifically, why is ordering not giving the position of the first element of Sort, when I ask for only the first element?

Note: I believe Ordering works correctly, when all elements of the list are $>0$, so the sorting function is perhaps the issue somehow.

Edit: Using

Ordering[{1, 2, .1, 0, -2, 3}, 1, 
 If[#1 > 0 && #2 > 0, #1 < #2, If[#1 > 0 && #2 <= 0, True, False]] &]

fixes it (for the MWE at least). I figured out that the If statement was throwing false when I did not expect it to due to the order of comparisons.

However I am still not sure why, in the original case, using there was not a problem for $n=2$.

$\endgroup$
2
$\begingroup$

Trace, or traceView2, will show the evaluations of the ordering function. It also confirms Lukas Lang's analysis of Ordering[list, 1, func].

One might try to infer the algorithm for n > 1:

The first two steps are the same as Lukas points out for n = 1. From this point, the difference will be that Ordering will construct a complete order instead of just finding the "minimum" (according to the ordering function). Thus the third step completes the order of {1, 2, 0.1} by comparing the last pair of the first three elements, 0.1 and 1. The next two steps construct a partial order of the remaining three elements, and the 6th step completes the order of {0, -2, 3}. The last step compares the maximal element of {1, 2, 0.1} and the minimal element of {0, -2, 3}, which completes the order of all the elements.

As Lukas has mentioned, if the ordering function satisfied the conditions for an ordering function (for instance, the transitive property), there is no need to compare further pairs of elements. In this case, if the list of numbers is shuffled, you can get different results.

Code:

Manipulate[
 Grid[{{
    Labeled[
     Graph[vv, Take[cmps, steps], 
      VertexLabels -> 
       Thread[vv -> Thread[Subscript[vv, Range@Length@vv]]],
      EdgeLabels -> 
       Take[Thread[cmps ->
          (Framed[Style[#, Red], Background -> LightBlue] & /@ 
            Range@Length@cmps)], steps],
      ImagePadding -> 20, ImageSize -> {350, 350}],
     Row[{"Next: ", 
       ReplacePart[RotateLeft@cmps, -1 -> "End"][[steps]]}],
     Top],
    Column[{" Steps "}~Join~Take[cmps, steps]]
    }}, Alignment -> Top, Dividers -> Center],
 {{n, 1}, {1, 2, 3, 4}, TrackingFunction -> (trackFN[#] &)},
 {{steps, 1}, 1, Dynamic@Length[cmps], 1},
 {{vv, {1, 2, .1, 0, -2, 3}}, None},
 {{cmps, cmps}, None}, {{trackFN, trackFN}, None},
 Initialization :> (
   trackFN = Function[n1,
     n = n1;
     cmps = Reap[
        Ordering[vv, n,
         With[{res = If[#1 > 0, #1 < #2, False]}, 
           If[res, Sow@DirectedEdge[#1, #2], 
            Sow[DirectedEdge[#2, #1]]]; res] &]
        ][[2, 1]];
     steps = Length@cmps;
     steps];
   trackFN[1])
 ]
$\endgroup$
1
  • $\begingroup$ This is great! Thank you very much $\endgroup$
    – user106860
    Aug 2 at 15:52
7
$\begingroup$

In short: Your ordering function is not a valid ordering function: Both func[-2,3] and func[3,-2] return False, so the two numbers cannot be sorted. Sorting-related functions might therefore return unexpected results.

As for the particular result you are seeing here: My guess is that Ordering[list, 1, func] calls a specialized implementation for improved performance. That implementation probably goes through the list once, keeping the minimal element (and its index): So it first calls func[1, 2] which in your case is True so 1 is before 2. Then it does func[1,0.1] which is False, so 0.1 comes before 1. It then continues with func[0.1,0] (False), func[0, -2] (False), and finally func[-2,3] which is also False, so 3 is before -2 and thus Orderingconcludes that 3 is the first element.

$\endgroup$
3
  • 2
    $\begingroup$ The key point here: "the ordering function is not a valid ordering function". If the ordering function isn't a proper ordering function then you shouldn't expect anything ordering related to be consistent for it $\endgroup$
    – b3m2a1
    Aug 1 at 8:53
  • $\begingroup$ About your second paragraph, I understand that. My question is specifically about -- and perhaps I could have made this more clear -- Ordering[list,1,p] and Ordering[list,2,p] give different smallest elements in the supplied MWE (with the former being inconsistent with the result from Sort). That is... somehow the (reported) "first" element is different when changing the 1 to a 2. I do recognize that what b3m2a1 pointed out does answer this though, albeit in a broad sense. $\endgroup$
    – user106860
    Aug 1 at 11:50
  • $\begingroup$ @user106860 as I've noted, my guess is that Ordering is special-cased for n=1 for increased performance, hence the different result. $\endgroup$
    – Lukas Lang
    Aug 1 at 11:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.