# Quicksort in APL Revisited

A message in the Forum inquired on sorting strings in APL with a custom comparison function.

First, sorting strings without a custom comparison function obtains with a terse expression:

``````      {⍵[⍋↑⍵]} 'syzygy' 'boustrophedon' 'kakistocracy' 'chthonic'
┌─────────────┬────────┬────────────┬──────┐
│boustrophedon│chthonic│kakistocracy│syzygy│
└─────────────┴────────┴────────────┴──────┘
``````

Sorting strings with a custom comparison function can also be accomplished succinctly by simple modifications to the Quicksort function

``````Q←{1≥≢⍵:⍵ ⋄ S←{⍺⌿⍨⍺ ⍺⍺ ⍵} ⋄ ⍵((∇<S)⍪=S⍪(∇>S))⍵⌷⍨?≢⍵}
``````

in a Dyalog blog post in 2014. A version that accepts a comparison function operand is:

``````QS←{1≥≢⍵:⍵ ⋄ (∇ ⍵⌿⍨0>s),(⍵⌿⍨0=s),∇ ⍵⌿⍨0<s←⍵ ⍺⍺¨ ⍵⌷⍨?≢⍵}
``````

The operand function `⍺ ⍺⍺ ⍵` is required to return `¯1`, `0`, or `1`, according to whether `⍺` is less than, equal to, or greater than `⍵`. In `QS`, the phrase `s←⍵ ⍺⍺¨ ⍵⌷⍨?≢⍵` compares each element of `⍵` against a randomly chosen pivot `⍵⌷⍨?≢⍵`; the function then applies recursively to the elements of `⍵` which are less than the pivot `(0>s)` and those which are greater than the pivot `(0<s)`.

Example with numbers:

``````      (×-)QS 3 1 4 1 5 9 2 6 5 3 5 8 97 9
1 1 2 3 3 4 5 5 5 6 8 9 9 97

3(×-)4
¯1
3(×-)3
0
3(×-)¯17
1
``````

Example with strings:

``````      strcmp←{⍺≡⍵:0 ⋄ ¯1*</⍋↑⍺ ⍵}

'syzygy' strcmp 'syzygy'
0
'syzygy' strcmp 'eleemosynary'
1
'syzygy' strcmp 'zumba'
¯1

strcmp QS 'syzygy' 'boustrophedon' 'kakistocracy' 'chthonic'
┌─────────────┬────────┬────────────┬──────┐
│boustrophedon│chthonic│kakistocracy│syzygy│
└─────────────┴────────┴────────────┴──────┘
``````

A more efficient string comparison function is left as an exercise for the reader. 🙂