OpenEuphoria

1. sort constants confusing

• Posted by petelomax Jun 09, 2017
• 2850 views

http://openeuphoria.org/docs/std_sort.html#_2964_sorting

I could not work out why there were 4 sort options. It reads, at best, like you have to use ASCENDING for sort() and NORMAL_ORDER for custom_sort().

As soon as I looked at the source, the penny dropped instantly.

Better yet, just bin two of them (I don't much care which).

Pete

3. Re: sort constants confusing

• Posted by Spock Jun 12, 2017
• 2778 views

Stranger still is this sheepish note in the documentation for sort(), custom_sort() and sort_columns():

"This function uses the "Shell" sort algorithm. This sort is not "stable", i.e. elements that are considered equal might change position relative to each other"

Really? Does \std still have unstable sort routines after all these years or was it fixed and someone just needs to update the documentation? I thought we had thrashed this out in 2014? In fact, it was indicated as far back as 2011 but nobody did anything about it.

Spock

5. Re: sort constants confusing

• Posted by DerekParnell (admin) Jul 02, 2017
• 2634 views

No idea now. Probably stupidity but that is not the salient lesson here, in my opinion.

The better question would be to ask why did such poor code get to stay in the distribution? I suspect that the answer to that relates to the lack of peer review before release packaging.

7. Re: sort constants confusing

• Posted by petelomax Jul 04, 2017
• 2610 views
• Last edited Jul 05, 2017

Let's not. There is nothing whatsoever wrong with any of the terms/constant names as given, the problem is just the implication that they are somehow different.

Having four constants implies (to my tiny brain) that there are four separate meanings, when in fact there are only two, which is as clear as can be in the source, but not in the documentation.

It is fair to say that someone would only ever notice this if they had not just looked at the source file.

Assuming that it is not practical to change eu2doc (or whatever it is called) to stop it from ripping out the "=" parts,
I think the simplest solution would just be to change, in std/sort.e itself:

--** The normal sort order used by the custom comparison routine. 
NORMAL_ORDER = ASCENDING, 

to

--** The normal sort order used by the custom comparison routine. (same as ASCENDING) 
NORMAL_ORDER = ASCENDING, 

and

--** Reverses the sense of the order returned by a custom comparison routine. 
REVERSE_ORDER = DESCENDING 

to

--** Reverses the sense of the order returned by a custom comparison routine. (same as DESCENDING) 
REVERSE_ORDER = DESCENDING 

I retract my suggestion to "bin two of em"

Pete

9. Re: sort constants confusing

• Posted by petelomax Jul 04, 2017
• 2616 views

From March this year: http://rosettacode.org/wiki/Compare_sorting_algorithms%27_performance#Phix

11. Re: sort constants confusing

• Posted by Spock Jul 04, 2017
• 2574 views
• Last edited Jul 05, 2017

The central routine in msort.zip first checks the size of the data set and then selects one of two options:

n < 200 (call fast insertion sort)
else (call merge sort supplemented with fast insertion sort)

So whatever n there is the sort performance is always good, always stable. And without the stability property sorting by column is not guaranteed to be correct - an important goal in the real-world. Quicksort and Shellsort [Edit: Heapsort too] are not naturally stable sorts.

It would be interesting to compare the performance of the Phix code on Rosetta versus msort but.. I couldn't get the former to work (something about blah blah Visual .. 2013 blah blah) so I gave up.

Spock

13. Re: sort constants confusing

• Posted by Spock Jul 04, 2017
• 2546 views

I installed it but the demo is still not running. Copying the dll to the various sub-folders of Phix didn't work either.

Spock

15. Re: sort constants confusing

• Posted by _tom (admin) Jul 07, 2017
• 2410 views

OK.

We can standardize on NATURAL and REVERSE; the other choices will be there just there to help define "natural." We naturally write from left to right, hence small to large. But, we are accustomed to writing numbers themselves in their "natural" Arabic form!

• Output is in natural order which is "sorted from small to large (ascending or rising)."

• The optional output is reverse order which is "sorted from large to small (descending or falling)."

_tom

17. Re: sort constants confusing

• Posted by Spock Jul 09, 2017
• 2375 views
• Last edited Jul 10, 2017

True. The normal order for sorting is ascending. Sort({3,1,5,2,4}) ought to result in {1,2,3,4,5} without any need to explicitly specify the order.

The algorithm(s) in msort.zip all produce ascending order results. To have it descending I simply reverse the result, eg:

s = reverse( sort(s, n) ) -- n is column ['coz I have lots of column sorting processes] 

However, because of the stability principle, this is not strictly the same as, eg:

s = sort(s, n, REVERSE) 

Nevertheless, YAGNI and Occam's razor

So in the end that would lead to, eg:

s = sort(s) 
s = sort_reverse(s) 

An optional parameter could give the desired column sorting.

Spock

19. Re: sort constants confusing

• Posted by _tom (admin) Jul 12, 2017
• 2247 views

Base on the input from above...

My suggestion:

• leave the std/sort.e alone for compatibility reasons
  eventually deprecate it?
• in the demo folder: provide a set of sort algorithms (from allsorts and rosetta code) for those that have special requirements
• for stable sorting add: http://www.rapideuphoria.com/msort.zip from Mike
• for natural sorting add: http://www.rapideuphoria.com/nat_sort.zip from Andy Serpa
• The new sorting.e library will work on OE and Phix.

My working sorting definitions are:

stable

• as found in msort but not in std/sort.e

rank

• as output by the compare function (larger or smaller) or custom_compare

direction

• UP or DN (default small to large )

order

• the resulting sorted sequence
  • default is numerical (mathematical number line)
  • ASCII order for historical reasons
  • unicode order is what UTF8 gives you
  • natural order (as in nat_sort.zip)
  • user defined for things like sorting playing cards

_tom

21. Re: sort constants confusing

• Posted by _tom (admin) Jul 19, 2017
• 2167 views

A demo of the new sorting include is: http://openeuphoria.org/pastey/293.wc

It provides stable sorting, column sorting, index sorting, along with number and natural order options. All sorts are in the up direction.

After changing a few identifiers this works on OE and Phix.

_tom

Forked into: Natural sort comparison

23. Re: sort constants confusing

• Posted by _tom (admin) Aug 01, 2017
• 2105 views

The English language is not helping at all. We are using words with fuzzy meanings. The word "natural" seems to be a particular problem when used to describe sorting.

The solution is going to be that a few words will be chosen and then defined for use within Euphoria--ignoring the use (and misuse) of the same words elsewhere.

The idea of "stable sorting" is important. Download http://www.rapideuphoria.com/msort.zip. Spock has explained "stable" clearly in the docs that come with Mike Sort.

Here is another idea for your consideration:

To sort values is "to order values into numerical order from small to large."

To collate values is "to order values into a logical order from small to large."

• We sort numbers

There are no arguments as to what number value comes next. Some people call this "natural order". Sorting "up" from small to large is also "natural."

the eu:compare function will sort number values without problem

• we collate alphanumeric values

Collated data does not have to be in number order. When ascii encoded characters are sorted in numerical order the alphabetic order may not agree with everyone's idea of the correct order. Thus we want a "custom sort" that puts characters, into what is for characters, a "natural order". Some call this "lexical order" to distinguish it from number sorting.

We need a custom algorithm to collate values. Collating must consider ascii and utf encoding for characters.

The problem is if I just use "natural" you can not be sure what I mean unless you look at a definition I create for exclusive use in OE.

_tom