View source for Using an ordering function when sorting

[[Category:Sorting Functions]]
[[Category:Doc Status D]] <!-- For Lumina use, do not change -->
''New to [[Analytica 7.2]]''

{{ReleaseBar}}

The sorting functions [[Sort]], [[SortIndex]] and [[Rank]] normally order values using Analytica's built-in ordering: numbers numerically, text alphabetically, and the various data types in a fixed relative order (see [[SortIndex#Descending]]). Occasionally that isn't the order you want. Each of these functions accepts an optional «lessThan» parameter: an ''ordering function'' of your own that decides, for any two items «x» and «y», whether «x» comes before «y».

== The ordering function ==
An ordering function accepts two parameters and returns true when the first item should be ordered before the second, and false otherwise (including when the two are equivalent). You can pass:
* a local (lambda) function written in place, e.g. <code>lessThan: (Function(x, y) ::= x->age < y->age)</code>
* the name of (or a handle to) a [[User-Defined Function]], e.g. <code>lessThan: VersionLess</code>
* a Python callable

For example, version numbers written as text sort alphabetically, which puts "1.10.0" before "1.9.0". An ordering function that compares them part by part fixes this:
 Function VersionKey(v : text atom) ::= 
 [[Local]] p := [[SplitText]](v, '.'); 
 [[ParseNumber]](Slice(p,1))*1e6 + [[ParseNumber]](Slice(p,2))*1e3 + [[ParseNumber]](Slice(p,3))

 Function VersionLess(x, y : text atom) ::= VersionKey(x) < VersionKey(y)

:<code>[[SortIndex]](['1.9.0', '1.10.0', '1.2.3', '2.0.0'], lessThan: VersionLess)</code> &rarr; 
::<code>['1.2.3', '1.9.0', '1.10.0', '2.0.0']</code>

The same «lessThan» parameter works in all three functions:
:<code>Sort(Versions, I, lessThan: VersionLess)</code>
:<code>Rank(Versions, I, lessThan: VersionLess)</code>

=== Requirements on the ordering ===
The function must define a consistent ordering: if it says «x» comes before «y», it must not also say «y» comes before «x», and if «x» is before «y» and «y» is before «z» then «x» must be before «z» (a ''strict weak ordering''). Items for which neither <code>lessThan(x, y)</code> nor <code>lessThan(y, x)</code> is true are tied. Ties keep their original order (the sort is stable), and [[Rank]] gives tied items the same rank (as controlled by its «type» parameter). An inconsistent ordering function won't crash, but the resulting order is arbitrary.

A "depends on" relation in a graph is a partial order, not a total one, so it doesn't qualify directly. To sort the nodes of a dependency graph in dependency order, compute a depth (or level) for each node first and compare depths.

== What is passed to the function ==
What «x» and «y» hold depends on how you declare the ordering function's first two parameters.

=== Atoms (the usual case) ===
When the parameters are undeclared, <code>(x, y)</code>, or declared as atoms, e.g. <code>(x, y : atom)</code> or <code>(x, y : text atom)</code>, the function receives one item at a time. If the array being sorted has indexes besides the sort index «I», [[Sort]], [[SortIndex]] or [[Rank]] [[Array Abstraction|array abstracts]] over them in the usual way, sorting each slice separately, and the ordering function only ever sees atoms. For example, with <code>A</code> indexed by <code>I</code>, <code>J</code> and <code>K</code>, <code>Sort(A, I, lessThan: f)</code> sorts each [J, K] slice along <code>I</code>.

When you also specify a «keyIndex» (a multi-key sort), an atom-valued ordering function is applied key by key, exactly as the built-in comparison is: the primary key (the first element along «keyIndex») decides, unless the function considers the two items tied, in which case the next key breaks the tie, and so on.

=== Whole key vectors ===
For a multi-key sort you may instead want to see all of the keys at once. Declare the first two parameters as 1-D vectors along the key index, and the function receives, for each of the two items, its entire vector of keys along «keyIndex»:
:<code>Sort(Data, Person, keyIndex: K, lessThan: (Function(x, y : [K]) ::= Sum(x, K) < Sum(y, K)))</code>
The index named in the declaration must be the «keyIndex» itself, or an error results. A user-defined function can instead take the key index as a parameter declared as <code>Index</code>, which receives the «keyIndex»:
:<code>Function RowSumLess(x, y : [KI] ; KI : Index) := Sum(x, KI) < Sum(y, KI)</code>
:<code>Sort(Data, Person, keyIndex: K, lessThan: RowSumLess)</code>
A parameter declared as <code>Vector</code> also receives the whole key vector. «keyIndex» is required for this form, and since the function then decides the order from all of the keys at once, «descending» must be a single boolean rather than an array indexed by «keyIndex».

Only atoms, or 1-D vectors along «keyIndex», are ever passed. The dimensionality you declare for the ordering function never changes how [[Sort]], [[SortIndex]] or [[Rank]] array abstract (that is fixed by their own parameter declarations), so a declaration such as <code>(x, y : [J, K])</code> is an error. To compare arbitrary slices, sort references to them instead:
:<code>Sort(\[J, K] A, I, lessThan: (Function(rx, ry : reference atom) ::= Sum(#rx, J, K) < Sum(#ry, J, K)))</code>

=== Other parameters ===
Beyond the first two parameters, the sorting function fills in only:
* a parameter declared as <code>Index</code>, which receives «keyIndex» (as above), and
* a parameter named «caseInsensitive», which receives the value passed to the sorting function's own «caseInsensitive» parameter.
Any other parameter of the ordering function must be optional.

== Null values ==
When an item is [[Null]] and the ordering function's parameters are declared with an atomic data type that excludes Null, such as <code>(x, y : text atom)</code>, the call short-circuits and returns Null without evaluating the function body, which is the standard behavior for atomic parameters. Whenever the ordering function returns Null (or Undefined) for a pair of items, the sorting function falls back to the built-in ordering for that pair, which places Null after everything else (or first when <code>descending: true</code>). So an ordering function with typed parameters gets the standard treatment of Null for free.

To decide the placement of Null yourself, leave the parameters untyped (or declare them <code>orNull</code>) so that Null is passed in. This puts Null values first:
:<code>SortIndex(D, I, lessThan: (Function(x, y) ::= (x = Null and y <> Null) or (x <> Null and y <> Null and x < y)))</code>

== Descending order ==
<code>descending: true</code> reverses the order that the function defines, so you don't need to write a second function for the reverse order. In a multi-key sort with an atom-valued ordering function, «descending» may be indexed by «keyIndex» as usual.

== Examples ==
Some orderings that are much easier with an ordering function:
* '''Version numbers''', so that 1.10.0 comes after 1.9.0 (above).
* '''Natural order''' for names with a number appended, so that x2 comes before x10:
:<code>Function NatLess(x, y : text atom) := Local px := SelectText(x, 1, 1); Local py := SelectText(y, 1, 1); px < py or (px = py and ParseNumber(SelectText(x, 2)) < ParseNumber(SelectText(y, 2)))</code>
* '''Pinning selected items to the top''', with the rest in alphabetical order:
:<code>Function PinLess(x, y : text atom) := Local px := Sum(Pinned = x, Pinned) > 0; Local py := Sum(Pinned = y, Pinned) > 0; (px and not py) or (px = py and x < y)</code>
* '''Changing the relative order of data types''', e.g. text before numbers:
:<code>SortIndex(D, I, lessThan: (Function(a, b) ::= (IsText(a) and not IsText(b)) or (IsText(a) = IsText(b) and a < b)))</code>
* '''Ordering [[Struct]] instances''' by a member:
:<code>Sort(People, I, lessThan: (Function(x, y) ::= x->age < y->age))</code>
* '''Sorting file paths by the file name''' only, keeping the full path:
:<code>Function FileNameOf(p : text atom) := Local parts := SplitText(p, '\'); Slice(parts, Size(parts))</code>
:<code>SortIndex(Paths, lessThan: (Function(x, y) ::= FileNameOf(x) < FileNameOf(y)))</code>
* '''Sorting handles''' to objects by an attribute:
:<code>SortIndex(Objs, lessThan: (Function(x, y) ::= (Title of x) < (Title of y)))</code>

Other orderings, such as an enumerated order (S, M, L, XL) or ordering by text length, are also easy without an ordering function, e.g. <code>SortIndex(@[Sizes = x], I)</code> or <code>SortIndex(TextLength(x), I)</code>. The «lessThan» form is still convenient with [[Sort]] and [[Rank]], where the values themselves stay in place.

== Performance ==
An ordering function is called O(''n'' log ''n'') times, and each call evaluates an Analytica expression, so sorting with one is considerably slower than the built-in comparison (on the order of 10<sup>5</sup> comparisons per second). When the order can be expressed as a computed key, <code>SortIndex(key, I)</code> is faster. Sorts that use an ordering function run single-threaded.

== History ==
* The «lessThan» parameter of [[Sort]], [[SortIndex]] and [[Rank]] was added in [[Analytica 7.2]].

== See Also ==
* [[Sort]]
* [[SortIndex]]
* [[Rank]]