Sorting strings

[alexeyv]

Hi,

I'm wandering how to sort the strings array in APL. For example in Common Lisp I could write something like this (given the sort and string< functions are part of the language):

Code: Select all

CL-USER 9 > (sort '("test" "this" "strings") #'string<)
("strings" "test" "this")


How can I do something similar, using custom comparison function? Just curious.

[Roger|Dyalog]

You mean like this?

Code: Select all

      {⍵[⍋↑⍵]} 'test' 'this' 'string'
┌──────┬────┬────┐
│string│test│this│
└──────┴────┴────┘
      {⍵[⍋↑⍵]} 'chthonic' 'boustrophedonic' 'sesquipedalian' 'kakistocracy'
┌───────────────┬────────┬────────────┬──────────────┐
│boustrophedonic│chthonic│kakistocracy│sesquipedalian│
└───────────────┴────────┴────────────┴──────────────┘


If you really do have a custom comparison function, a custom sort can be derived readily from an APL implementation of Quicksort.

[Roger|Dyalog]

Herewith, a Quicksort with a custom comparison function. In the Dyalog blog post, Quicksort is defined as follows:

Code: Select all

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


A version that accepts a comparison function operand is:

Code: Select all

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 ⍵. The phrase s←⍵ ⍺⍺¨ ⍵⌷⍨?≢⍵ compares each element of ⍵ against a randomly chosen pivot ⍵⌷⍨?≢⍵. The function then recursively applies to the elements of ⍵ which are less than the pivot (0>s) and those which are greater than the pivot (0<s).

For example:

Code: Select all

      (×-)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


A string example:

Code: Select all

      strcmp←{⍺≡⍵:0 ⋄ ¯1*(⍳2)≡⍋↑⍺ ⍵}
      'syzygy' strcmp 'syzygy'
0
      'syzygy' strcmp 'eleemosynary'
1
      'syzygy' strcmp 'tom'
¯1

      strcmp QS 'chthonic' 'boustrophedonic' 'sesquipedalian' 'kakistocracy'
┌───────────────┬────────┬────────────┬──────────────┐
│boustrophedonic│chthonic│kakistocracy│sesquipedalian│
└───────────────┴────────┴────────────┴──────────────┘


A more efficient string comparison function is left as an exercise for the reader. :-)

[alexeyv]

Thanks :) So as I understand the basic idea is just to reimplement ⍋ with custom function.

[Morten|Dyalog]

In a sense... But in the Dyalog interpreter,⍋ quickly switches to hashing and other "clever" techniques depending on data type, range, etc.

[Roger|Dyalog]

If you have a sort that accepts a custom comparison function (as per your request), then you are limited to comparison sorting. However, depending on the data, there are other sorting algorithms.

As an extreme example, how do you sort a boolean vector?

Code: Select all

      bitsort←{0 1⌿⍨c,⍨(≢⍵)-c←+/⍵}
      bitsort ⎕io<?17⍴5
0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1


This would beat any comparison sort. No contest.

[alexeyv]

Yes, I understand. I'm just trying to investigate APL-ways to solve problems which I use to solve using functional programming approach, i.e. by composing different functions; also interesting to see how can I work with APL with the data like strings of different length.