Grade: Difference between revisions
m (→Other: Fix duplicated link to Roger's post) |
m (Text replacement - "<source" to "<syntaxhighlight") |
||
| Line 1: | Line 1: | ||
{{Built-ins|Grade|⍋|⍒}} is a pair of [[ambivalent]] [[primitive function|primitive functions]] related to [[wikipedia:sorting#sorting information or data|sorting]]. Instead of sorting the given array directly, Grade returns a [[permutation]] [[vector]] whose length equals the number of [[major cell|major cells]], so that [[indexing]] into the argument gives the sorted array. The [[glyph]] < | {{Built-ins|Grade|⍋|⍒}} is a pair of [[ambivalent]] [[primitive function|primitive functions]] related to [[wikipedia:sorting#sorting information or data|sorting]]. Instead of sorting the given array directly, Grade returns a [[permutation]] [[vector]] whose length equals the number of [[major cell|major cells]], so that [[indexing]] into the argument gives the sorted array. The [[glyph]] <syntaxhighlight lang=apl inline>⍋</source> is called '''Grade Up''' and gives the ascending sort order, while <syntaxhighlight lang=apl inline>⍒</source> is called '''Grade Down''' and gives the descending sort order. | ||
== Monadic form == | == Monadic form == | ||
| Line 5: | Line 5: | ||
[[Monadic]] Grade returns the sorting order of the major cells of the [[argument]]. [[Indexing]] into the original argument gives the sorted array; indexing into another array gives the result commonly known as '''Sort By'''. | [[Monadic]] Grade returns the sorting order of the major cells of the [[argument]]. [[Indexing]] into the original argument gives the sorted array; indexing into another array gives the result commonly known as '''Sort By'''. | ||
< | <syntaxhighlight lang=apl> | ||
⎕←A←↑'foo' 'bar' 'baz' ⍝ A character matrix | ⎕←A←↑'foo' 'bar' 'baz' ⍝ A character matrix | ||
foo | foo | ||
| Line 31: | Line 31: | ||
Grade performs [[wikipedia:sorting algorithm#stability|stable sorting]], so that the indices of the repeated major cells are sorted by the order of appearance. Because of this, Grade Down produces the reverse of Grade Up only if all the major cells are unique. | Grade performs [[wikipedia:sorting algorithm#stability|stable sorting]], so that the indices of the repeated major cells are sorted by the order of appearance. Because of this, Grade Down produces the reverse of Grade Up only if all the major cells are unique. | ||
< | <syntaxhighlight lang=apl> | ||
S←6 10 10 3 2 15 ⋄ T←S,¨⍳6 | S←6 10 10 3 2 15 ⋄ T←S,¨⍳6 | ||
⍝ Note that the order of two 10s are preserved in both cases | ⍝ Note that the order of two 10s are preserved in both cases | ||
| Line 50: | Line 50: | ||
[[Dyalog APL]] supports [[total array ordering]] when comparing [[nested array|nested arrays]] of possibly different [[shape]] and [[type]]. Grade is the only built-in function which can perform comparisons between arbitrary arrays of previously unknown order ([[Interval Index]] requires the left argument to be sorted beforehand). | [[Dyalog APL]] supports [[total array ordering]] when comparing [[nested array|nested arrays]] of possibly different [[shape]] and [[type]]. Grade is the only built-in function which can perform comparisons between arbitrary arrays of previously unknown order ([[Interval Index]] requires the left argument to be sorted beforehand). | ||
< | <syntaxhighlight lang=apl> | ||
⎕←A←(1(⍪2 3)) (1 3) (⊂0 1 2) | ⎕←A←(1(⍪2 3)) (1 3) (⊂0 1 2) | ||
┌─────┬───┬───────┐ | ┌─────┬───┬───────┐ | ||
| Line 66: | Line 66: | ||
[[Dyadic]] Grade is limited to [[simple]] [[character]] array arguments. The left argument specifies the collation order to use when sorting the right argument. | [[Dyadic]] Grade is limited to [[simple]] [[character]] array arguments. The left argument specifies the collation order to use when sorting the right argument. | ||
If the left argument is a [[vector]], the sorting order is simply the order of appearance in the left argument. In other words, < | If the left argument is a [[vector]], the sorting order is simply the order of appearance in the left argument. In other words, <syntaxhighlight lang=apl inline>X⍋Y</source> equals <syntaxhighlight lang=apl inline>⍋X⍳Y</source>, and same for <syntaxhighlight lang=apl inline>⍒</source>. | ||
< | <syntaxhighlight lang=apl> | ||
⎕A⍋'ZAM,.BIA' ⍝ Alphabetical order, garbage goes last | ⎕A⍋'ZAM,.BIA' ⍝ Alphabetical order, garbage goes last | ||
2 8 6 7 3 1 4 5 | 2 8 6 7 3 1 4 5 | ||
| Line 77: | Line 77: | ||
If the left argument is a higher-[[rank]] array, sorting is done in multiple stages. The last [[axis]] of X takes highest precedence, then the next-to-last, and so on, giving ties to all characters that appear at the same index over the current axis. A notable application is case-insensitive sorting. | If the left argument is a higher-[[rank]] array, sorting is done in multiple stages. The last [[axis]] of X takes highest precedence, then the next-to-last, and so on, giving ties to all characters that appear at the same index over the current axis. A notable application is case-insensitive sorting. | ||
< | <syntaxhighlight lang=apl> | ||
Data | Data | ||
ABLE | ABLE | ||
| Line 99: | Line 99: | ||
</source> | </source> | ||
[[J]] does not implement dyadic grade, but provides '''Sort By''' as the dyadic counterparts of < | [[J]] does not implement dyadic grade, but provides '''Sort By''' as the dyadic counterparts of <syntaxhighlight lang=j inline>/:</source> and <syntaxhighlight lang=j inline>\:</source> instead. | ||
== External links == | == External links == | ||
Revision as of 21:08, 10 September 2022
⍋ ⍒
|
Grade (⍋, ⍒) is a pair of ambivalent primitive functions related to sorting. Instead of sorting the given array directly, Grade returns a permutation vector whose length equals the number of major cells, so that indexing into the argument gives the sorted array. The glyph <syntaxhighlight lang=apl inline>⍋</source> is called Grade Up and gives the ascending sort order, while <syntaxhighlight lang=apl inline>⍒</source> is called Grade Down and gives the descending sort order.
Monadic form
Monadic Grade returns the sorting order of the major cells of the argument. Indexing into the original argument gives the sorted array; indexing into another array gives the result commonly known as Sort By.
<syntaxhighlight lang=apl>
⎕←A←↑'foo' 'bar' 'baz' ⍝ A character matrix
foo bar baz
⍋A ⍝ Grade up its rows
2 3 1
A[⍋A;] ⍝ Move the rows to sorted order (ascending)
bar baz foo
⍒A ⍝ Grade down its rows
1 3 2
A[⍒A;] ⍝ Move the rows to sorted order (descending)
foo baz bar
B←15 10 5
A[⍋B;] ⍝ Sort A by B
baz bar foo </source>
Grade performs stable sorting, so that the indices of the repeated major cells are sorted by the order of appearance. Because of this, Grade Down produces the reverse of Grade Up only if all the major cells are unique.
<syntaxhighlight lang=apl>
S←6 10 10 3 2 15 ⋄ T←S,¨⍳6
⍝ Note that the order of two 10s are preserved in both cases
(⍋S) (T[⍋S])
┌───────────┬────────────────────────────┐ │5 4 1 2 3 6│┌───┬───┬───┬────┬────┬────┐│ │ ││2 5│3 4│6 1│10 2│10 3│15 6││ │ │└───┴───┴───┴────┴────┴────┘│ └───────────┴────────────────────────────┘
(⍒S) (T[⍒S])
┌───────────┬────────────────────────────┐ │6 2 3 1 4 5│┌────┬────┬────┬───┬───┬───┐│ │ ││15 6│10 2│10 3│6 1│3 4│2 5││ │ │└────┴────┴────┴───┴───┴───┘│ └───────────┴────────────────────────────┘ </source>
Dyalog APL supports total array ordering when comparing nested arrays of possibly different shape and type. Grade is the only built-in function which can perform comparisons between arbitrary arrays of previously unknown order (Interval Index requires the left argument to be sorted beforehand).
<syntaxhighlight lang=apl>
⎕←A←(1(⍪2 3)) (1 3) (⊂0 1 2)
┌─────┬───┬───────┐ │┌─┬─┐│1 3│┌─────┐│ ││1│2││ ││0 1 2││ ││ │3││ │└─────┘│ │└─┴─┘│ │ │ └─────┴───┴───────┘
⍋A
3 1 2
</source>
Dyadic form
Dyadic Grade is limited to simple character array arguments. The left argument specifies the collation order to use when sorting the right argument.
If the left argument is a vector, the sorting order is simply the order of appearance in the left argument. In other words, <syntaxhighlight lang=apl inline>X⍋Y</source> equals <syntaxhighlight lang=apl inline>⍋X⍳Y</source>, and same for <syntaxhighlight lang=apl inline>⍒</source>.
<syntaxhighlight lang=apl>
⎕A⍋'ZAM,.BIA' ⍝ Alphabetical order, garbage goes last
2 8 6 7 3 1 4 5
(⌽⎕A)⍋'ZAM,.BIA' ⍝ Reverse alphabetical order, garbage still goes last
1 3 7 6 2 8 4 5 </source>
If the left argument is a higher-rank array, sorting is done in multiple stages. The last axis of X takes highest precedence, then the next-to-last, and so on, giving ties to all characters that appear at the same index over the current axis. A notable application is case-insensitive sorting.
<syntaxhighlight lang=apl>
Data
ABLE aBLE ACRE ABEL aBEL ACES
Coll
ABCDEFGHIJKLMNOPQRSTUVWXYZ abcdefghijklmnopqrstuvwxyz
Coll⍋Data
4 5 1 2 6 3
Data[Coll⍋Data;]
ABEL aBEL ABLE aBLE ACES ACRE </source>
J does not implement dyadic grade, but provides Sort By as the dyadic counterparts of <syntaxhighlight lang=j inline>/:</source> and <syntaxhighlight lang=j inline>\:</source> instead.
External links
Documentation
- Dyalog Grade Up Monadic, Grade Down Monadic, Grade Up Dyadic, Grade Down Dyadic
- APLX Grade Up, Grade Down
- J Dictionary Grade Up, Grade Down, NuVoc Grade
- BQN
Other
- APL Cultivation lesson
- Dyadic Grade by Roger Hui, Dyalog Blog
- abrudz/Sort library: Examples of sorting variations (Classic, Natural, Danish, Finnish, German) using dyadic grade