Sorting strings
7 posts
• Page 1 of 1
Sorting strings
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):
How can I do something similar, using custom comparison function? Just curious.
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: 56
- Joined: Tue Nov 17, 2015 4:18 pm
Re: Sorting strings
You mean like this?
If you really do have a custom comparison function, a custom sort can be derived readily from an APL implementation of Quicksort.
- 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: 238
- Joined: Thu Jul 28, 2011 10:53 am
Re: Sorting strings
Herewith, a Quicksort with a custom comparison function. In the Dyalog blog post, Quicksort is defined as follows:
A version that accepts a comparison function operand is:
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:
A string example:
A more efficient string comparison function is left as an exercise for the reader. :-)
- 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: 238
- Joined: Thu Jul 28, 2011 10:53 am
Re: Sorting strings
Thanks :) So as I understand the basic idea is just to reimplement ⍋ with custom function.
- alexeyv
- Posts: 56
- Joined: Tue Nov 17, 2015 4:18 pm
Re: Sorting strings
In a sense... But in the Dyalog interpreter,⍋ quickly switches to hashing and other "clever" techniques depending on data type, range, etc.
-
Morten|Dyalog - Posts: 453
- Joined: Tue Sep 09, 2008 3:52 pm
Re: Sorting strings
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?
This would beat any comparison sort. No contest.
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: 238
- Joined: Thu Jul 28, 2011 10:53 am
Re: Sorting strings
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: 56
- Joined: Tue Nov 17, 2015 4:18 pm
7 posts
• Page 1 of 1
Who is online
Users browsing this forum: No registered users and 1 guest
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group