Skip to content

Sorting

Sorting is good. Grading is better.

Sorting lists and tables

For list, dictionary or table x, and symbol vector c of column names

direction list table
ascending asc x c xasc x
descending desc x c xdesc x

return sorted lists, dictionaries and tables. 

q)names:`jean`tom`khiloni`maria`raja`farokh`xin
q)scores:6 1 8 5 4 9 2

q)asc names
`s#`farokh`jean`khiloni`maria`raja`tom`xin
q)desc scores
9 8 6 5 4 2 1

q)desc names!scores
farokh | 9
khiloni| 8
jean   | 6
maria  | 5
raja   | 4
xin    | 2
tom    | 1

q)`scores xdesc ([]names;scores)
names   scores
--------------
farokh  9
khiloni 8
jean    6
maria   5
raja    4
xin     2
tom     1

Grading

Sorting a list is useful; grading it even more so.

Why?

Sorting a list returns it in sorted order. Grading it tells you the indexes to apply in order to sort it.

 asc x   <===>   x iasc x
desc x   <===>   x idesc x

The intermediate step allows us to sort one list by the items in another: y idesc x. 

q)names 3#idesc scores  / gold, silver, bronze
`farokh`khiloni`jean
Grading (iasc and idesc) maps the raw list to the sorted one.

Grading returns a list of indices. The indices of a dictionary are its keys. 

q)3#idesc names!scores   / gold, silver, bronze
`farokh`khiloni`jean

Ranking

Ranking maps the sorted list back to the raw list: rank x tells you where each item of x appears in the sorted list.2

rank x   <===>   asc[x]?x
x        <===>   asc[x] rank x


q)([]names;scores;rnk:rank scores)
names   scores rnk
------------------
jean    6      4
tom     1      0
khiloni 8      5
maria   5      3
raja    4      2
farokh  9      6
xin     2      1
Above, the rnk column shows each score’s position in the (ascending) sorted list.

rank x   <===>   iasc iasc x

Sortable

Data types 1–19 are all sortable.

Nested lists of uniform type1 are sorted into lexical order.

q)q:`sting`stole`stolen`steal`steel`stamp
q)asc string q
"stamp"
"steal"
"steel"
"sting"
"stole"
"stolen"
Above, the strings were sorted by their first items (all "s"), then their second items (all "t"), then their third items, and so on.

A symbol vector is sorted on the same principle. 

q)string asc q
"stamp"
"steal"
"steel"
"sting"
"stole"
"stolen"

Sorting a general list

A general list is sorted first into atoms and lists; then by the types of its items; then within each type.

q)q:("foo";"bar";`baz;`sheep`cow`cat;`abc;42; 17;`hen`duck;3.14;0b;1b;0b;2022.09m)

q)1 type'\q
"foo" "bar" `baz `sheep`cow`cat `abc 42 17 `hen`duck 3.14 0b 1b 0b 2022.09m
10    10    -11  11             -11  -7 -7 11        -9   -1 -1 -1 -13

q)asc q
0b
0b
1b
17
42
3.14
`abc
`baz
2022.09m
"bar"
"foo"
`hen`duck
`sheep`cow`cat
Note that the vectors, once grouped by type, are sorted into lexical order, but the individual vectors remain unsorted, e.g. "bar" and `hen`duck.

Grouping

List or dictionary

The result of group x is a dictionary with the nub (distinct items) of x as its key, and lists of indexes of x as its value. 

q)group "mississippi"
m| ,0
i| 1 4 7 10
s| 2 3 5 6
p| 8 9

q)gold:0010010b   / flag Gold Club members
q)group names!gold
0| `jean`tom`maria`raja`xin
1| `khiloni`farokh

Table by columns

Where

  • x is a table
  • c is a symbol atom or vector of colmn names of x

then c xgroup x returns a keyed table (dictionary) of which the key is the nub of x`c and items of the other columns are lists of values for the rows which have that value for column/s c. 

q)`gold xgroup ([]names;scores;gold)
gold| names                    scores
----| ----------------------------------
0   | `jean`tom`maria`raja`xin 6 1 5 4 2
1   | `khiloni`farokh          8 9

Exercises

No peeking.

Attempt each exercise before looking at its answer.

The exercises clarify your thinking. Reading answers does not.

  1. Sort names!scores alphabetically by name.

    Answer 
    q)names!scores
jean   | 6
tom    | 1
khiloni| 8
maria  | 5
raja   | 4
farokh | 9
xin    | 2

q){x asc key x}names!scores   / values in order of ascending keys
9 6 8 5 4 1 2

q){k!x k:asc key x}names!scores
farokh | 9
jean   | 6
khiloni| 8
maria  | 5
raja   | 4
tom    | 1
xin    | 2

  2. How do asc, desc, iasc, and idesc sort a table?

    Answer

    Keywords asc, desc, iasc, and idesc sort the first column of a table argument. 

    q)desc ([]names;scores)
names   scores
--------------
xin     2
tom     1
raja    4
maria   5
khiloni 8
jean    6
farokh  9

  3. Messages are queued from your customers, but you must serve the Gold Club members first. Write an expression that returns customer names in the order that you will serve them. 

    q)([]names;gold)
names   gold
------------
jean    0
tom     0
khiloni 1
maria   0
raja    0
farokh  1
xin     0
    Answer 
    q)gold:0010010b
q)([]names;gold)
names   gold
------------
jean    0
tom     0
khiloni 1
maria   0
raja    0
farokh  1
xin     0

q)idesc gold
2 5 0 1 3 4 6
q)names idesc gold
`khiloni`farokh`jean`tom`maria`raja`xin

  4. Produce a table of scores as shown in Ranking but with the highest scores ranked top.

    Answer

    We saw rank scores gave us rankings for an ascending sort. We also saw that rank x could be replaced by iasc iasc x.

    q)([]names;scores;rnk:iasc idesc scores)
names   scores rnk
------------------
jean    6      2
tom     1      6
khiloni 8      1
maria   5      3
raja    4      4
farokh  9      0
xin     2      5

  5. A perfect riffle shuffle divides a list into two equal parts, then interleaves consecutive items from each part. Write a riffle-shuffle function rs such that 

    q)rs "abcdef"
"adbecf"
q)rs til 6
0 3 1 4 2 5
    Answer

    This is a classic APL phrase, written

    {⍵[⍋⍋(⍴⍵)⍴0 1]}
    The heart of it takes a boolean list the length of the argument (⍴⍵)⍴0 1, grades it twice ⍋⍋, and indexes the function argument ⍵ with that.

    In q: 

    q){count[x]#01b}"abcdef"
010101b
q){iasc count[x]#01b}"abcdef"
0 2 4 1 3 5
    The first application of iasc returns all the even indices followed by all the odd indices. (Notice that the sort is stable, so the even indices keep their order, as do the odds.)

    The second iasc tells us how to sort this list; i.e. pick the first, fourth, second, fifth, and so on. 

    q){2 iasc/count[x]#01b}"abcdef"
0 3 1 4 2 5
    Indexing x with that is the riffle shuffle. 
    q){x 2 iasc/count[x]#01b}"abcdef"
"adbecf"
    Of course 
    iasc iasc x   <===>   rank x
    So 
    q)rs:{x rank count[x]#01b}
q)rs til 6
0 3 1 4 2 5

  6. Explain the following.

    q)group([]names;scores;gold)
names   scores gold|
-------------------| -
jean    6      0   | 0
tom     1      0   | 1
khiloni 8      1   | 2
maria   5      0   | 3
raja    4      0   | 4
farokh  9      1   | 5
xin     2      0   | 6
    Answer

    The table x is a list of like dictionaries, so its nub (distinct x) is also a list of like dictionaries, and thus also a table. So the key of the dictionary result of group x is a table.

    The table contains no duplicates, so the nub is the entire table. The dictionary value is the list of indices for each row. Each row is unique, so:

    q)q:([]names;scores;gold)
q)group[q] ~ q!1#'til count q
1b

  7. Write a lambda3 fc that returns a frequency count of the items of its argument x as a dictionary in which the key is the distinct items of x and the value is the number of times each key occurs in x. E.g.

    q)fc "mississippi"
m| 1
i| 4
s| 4
p| 2
    Answer 
    q)group "mississippi"
m| ,0
i| 1 4 7 10
s| 2 3 5 6
p| 8 9

q)fc:count each group ::   / {count each group x}
q)fc "mississippi"
m| 1
i| 4
s| 4
p| 2

  1. This includes matrices, which are rectangular nested lists of uniform type. ↩

  2. Despite its name, keyword rank has nothing to do with the rank of a function or list. Sorry. ↩

  3. Or a composition. ↩