Sorting strings

Learning APL or new to Dyalog? Ask "silly" questions here, without fear...

Sorting strings

Postby alexeyv on Wed Feb 24, 2016 9:53 pm

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.
alexeyv
 
Posts: 54
Joined: Tue Nov 17, 2015 4:18 pm

Re: Sorting strings

Postby Roger|Dyalog on Thu Feb 25, 2016 5:08 am

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
 
Posts: 139
Joined: Thu Jul 28, 2011 10:53 am

Re: Sorting strings

Postby Roger|Dyalog on Thu Feb 25, 2016 5:34 am

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. :-)
Roger|Dyalog
 
Posts: 139
Joined: Thu Jul 28, 2011 10:53 am

Re: Sorting strings

Postby alexeyv on Sun Feb 28, 2016 6:42 pm

Thanks :) So as I understand the basic idea is just to reimplement ⍋ with custom function.
alexeyv
 
Posts: 54
Joined: Tue Nov 17, 2015 4:18 pm

Re: Sorting strings

Postby Morten|Dyalog on Mon Feb 29, 2016 8:08 am

In a sense... But in the Dyalog interpreter,⍋ quickly switches to hashing and other "clever" techniques depending on data type, range, etc.
User avatar
Morten|Dyalog
 
Posts: 339
Joined: Tue Sep 09, 2008 3:52 pm

Re: Sorting strings

Postby Roger|Dyalog on Mon Feb 29, 2016 11:22 pm

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.
Roger|Dyalog
 
Posts: 139
Joined: Thu Jul 28, 2011 10:53 am

Re: Sorting strings

Postby alexeyv on Wed Mar 02, 2016 8:17 pm

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.
alexeyv
 
Posts: 54
Joined: Tue Nov 17, 2015 4:18 pm


Return to New to Dyalog?

Who is online

Users browsing this forum: No registered users and 1 guest