Sort

From APL Wiki
Jump to navigation Jump to search

Sort Up and Sort Down are monadic functions that order the major cells of an array in ascending or descending order. Traditionally these functions are performed using Grade in APL: for example the FinnAPL idiom library gives X[⍋X] and X[⍒X] to sort X ascending and descending, respectively. In several dialects or other array languages they are defined as primitives, but with widely varying glyphs: ∧∨ Extended Dyalog APL, Kap, and BQN, <> in dzaima/APL, and ≤≥ in Dyalog APL Vision, as well as ^ for ascending sort in K9 and Goal.

In Dyalog APL there are several recognized idioms for sorting: for ascending sorting, {⍵[⍋⍵]} and {⍵[⍋⍵;]} to sort rank 1 and 2 arrays specifically, and {(⊂⍋⍵)⌷⍵} to sort any rank (all idioms have the same performance; the rank-specific ones were defined first and are shorter). The same idioms are recognized for descending sorting, replacing ⍋ with ⍒.

Sorting with Grade is easiest using the Select (⊇) or From function, which for example allows the ascending sort function on any rank to be written as the train ⍋⊇⊢ in dzaima/APL. Using Reverse Compose ⍛ as implemented in Kap or Dyalog APL Vision, it can be written ⍋⍛⊇. In J, it's implemented as Sort By (/: for ascending) with Commute, /:~.

A dedicated sorting implementation can be substantially faster than grade and selection both because sorting is generally faster than grade (particularly for long vectors with small-width elements, where an index may take more storage space than an element) and because selection is cache-unfriendly. For small-range data, a moveless variant of counting sort is possible for sorting but not grading.[1] Flags for sorted data, which can be used to optimize various operations on the flagged array, can more easily be set with a dedicated sorting function.[2]

Documentation

References

  1. ↑ Marshall Lochbaum. Implementation of ordering functions. BQN implementation notes.
  2. ↑ Marshall Lochbaum. Sortedness flags in primitive implementation. BQN implementation notes.
APL built-ins [edit]
Primitives (Timeline) Functions
Scalar
Monadic Conjugate ∙ Negate ∙ Signum ∙ Reciprocal ∙ Magnitude ∙ Exponential ∙ Natural Logarithm ∙ Floor ∙ Ceiling ∙ Factorial ∙ Not ∙ Pi Times ∙ Roll ∙ Type ∙ Imaginary ∙ Square Root ∙ Round
Dyadic Add ∙ Subtract ∙ Times ∙ Divide ∙ Residue ∙ Power ∙ Logarithm ∙ Minimum ∙ Maximum ∙ Binomial ∙ Comparison functions ∙ Boolean functions (And, Or, Nand, Nor) ∙ GCD ∙ LCM ∙ Circular ∙ Complex ∙ Root
Non-Scalar
Structural Shape ∙ Reshape ∙ Tally ∙ Depth ∙ Ravel ∙ Enlist ∙ Table ∙ Catenate ∙ Reverse ∙ Rotate ∙ Transpose ∙ Raze ∙ Mix ∙ Split ∙ Enclose ∙ Nest ∙ Cut (K) ∙ Pair ∙ Link ∙ Partitioned Enclose ∙ Partition
Selection First ∙ Pick ∙ Take ∙ Drop ∙ Unique ∙ Identity ∙ Stop ∙ Select ∙ Replicate ∙ Expand ∙ Set functions (Intersection ∙ Union ∙ Without) ∙ Bracket indexing ∙ Index ∙ Cartesian Product ∙ Sort
Selector Index generator ∙ Grade ∙ Index Of ∙ Interval Index ∙ Indices ∙ Deal ∙ Prefix and suffix vectors
Computational Match ∙ Not Match ∙ Membership ∙ Find ∙ Nub Sieve ∙ Encode ∙ Decode ∙ Matrix Inverse ∙ Matrix Divide ∙ Format ∙ Execute ∙ Materialise ∙ Range
Operators Monadic Each ∙ Commute ∙ Constant ∙ Replicate ∙ Expand ∙ Reduce ∙ Windowed Reduce ∙ Scan ∙ Outer Product ∙ Key ∙ I-Beam ∙ Spawn ∙ Function axis ∙ Identity (Null, Ident)
Dyadic Bind ∙ Compositions (Compose, Reverse Compose, Beside, Withe, Atop, Over) ∙ Inner Product ∙ Determinant ∙ Power ∙ At ∙ Under ∙ Rank ∙ Depth ∙ Variant ∙ Stencil ∙ Cut ∙ Direct definition (operator) ∙ Identity (Lev, Dex)
Quad names Index origin ∙ Comparison tolerance ∙ Migration level ∙ Atomic vector
Retrieved from ‘https://aplwiki.com/index.php?title=Sort&oldid=11191’