From APL Wiki
(Redirected from Sort up)
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]



APL built-ins [edit]
Primitives (Timeline) Functions
Monadic ConjugateNegateSignumReciprocalMagnitudeExponentialNatural LogarithmFloorCeilingFactorialNotPi TimesRollTypeImaginarySquare Root
Dyadic AddSubtractTimesDivideResiduePowerLogarithmMinimumMaximumBinomialComparison functionsBoolean functions (And, Or, Nand, Nor) ∙ GCDLCMCircularComplexRoot
Structural ShapeReshapeTallyDepthRavelEnlistTableCatenateReverseRotateTransposeRazeMixSplitEncloseNestCut (K)PairLinkPartitioned EnclosePartition
Selection FirstPickTakeDropUniqueIdentityStopSelectReplicateExpandSet functions (IntersectionUnionWithout) ∙ Bracket indexingIndexCartesian ProductSort
Selector Index generatorGradeIndex OfInterval IndexIndicesDealPrefix and suffix vectors
Computational MatchNot MatchMembershipFindNub SieveEncodeDecodeMatrix InverseMatrix DivideFormatExecuteMaterialiseRange
Operators Monadic EachCommuteConstantReplicateExpandReduceWindowed ReduceScanOuter ProductKeyI-BeamSpawnFunction axis
Dyadic BindCompositions (Compose, Reverse Compose, Beside, Withe, Atop, Over) ∙ Inner ProductDeterminantPowerAtUnderRankDepthVariantStencilCutDirect definition (operator)
Quad names Index originComparison toleranceMigration levelAtomic vector