On Sep 1, 2:29 pm, Dennis Ruffer
speakeasy.net> wrote:> On 2008-08-30 17:05:38 -0500, Jonah Thomas
gmail.com> said:
>>> Elizabeth D Rather
forth.com> wrote:>>> The FSL (or other collections, which I wish existed) is the
>>> right place for such things. Not the Standard.
>
>> A long time ago there was a Forth sort competition. I vaguely remember
>> that a Batcher sort won that competition, because of the particular
>> demands and how they were weighted.
>
>> Wasn't all the code declared public domain? It ought to be possible to
>> collect it and maybe update a little of it from Forth-83 and make a sort
>> library.
>
>> I'd do some or all of the work unless somebody says it isn't worth
>> doing. We could have a library of sort routines.
>
> Jet,
>
> I have a version of the Divide and Konker Sort
>
> \ The Divide and Konker sort was submitted as a reply to FIG's Contest
> \ of Sorts in Forth Demensions Sept/Oct 1989 by:
> \ Dwight K. Elvey
> \ 1300 Warren Drive
> \ Santa Cruz, CA 95060
>
> It is embedded in a copy of Forth, Inc.'s Data Base Support package
> which they shipped with polyFORTH. I was close to convincing Leon and
> Elizabeth to make that system public domain before I lost my last job.
> If the FSL is going to open up as a maintained library, that might be a
> good place to put it.
>
> As with most sorts, there are memory allocation issues involved with
> handling a data set that is worth sorting. A file based approach
> seemed to me to be the best compromise, which is why it ended up being
> combined.
>
> I can do some work on it or send the files to who ever might have the
> ambition to move them into yet another environment. I've moved this
> source to many environments, the latest being the IntellaSys T18
> compiler. I haven't looked at the FSL for many years, but I'd gladly
> help move it, if that would be useful.
>
> Write me offline at druf...@
worldnet.att.net so we can decide what is
> needed to get started.
>
> DaR
Hi
I wrote "Divide and Konker". It is a simple ratix 256 basket sort. It
does
require additional memory space compared with "in-place" sorts like
quicksort
but it is so much faster on things like intergers that it is worth
dealling
with.
A faster sort ( I sent a letter to the editor a month or two later )
is
a 256 radixed distribution sort. It was even faster and used less
memory
space.
I recall playing with these sorts on my NC4000 chip. I could sort a
1Kx16
bit signed integer array in 19.2 ms using a 4MHz clock.
Without using pointers, the distribution sort takes one array of 256
elements
to keep tallies and one additional temporary array to hold the same
number elements
as in the original array.
Both sorts have the advantage that one can reorder the sorts for
almost
zero additional time. For instance, say one wanted to do an ASCII sort
but
wanted to sort lowercase letters before upper case or sort numbers
after
letters. Any number of reordering can be handled at one time. This
would
be quite expensive to do in quicksort since the ordering would need to
be
determined for each element as it was being sorted or some method of
remapping
the elements prior to the sort.
Both sorts begin to have higher cost in time as the width of the sort
becomes
larger. For the distribution sort, the radix 256 is still the most
prcatical
although a radix of the square root of the width of the data is
fastest.
It would still sort things like hundreds of thousands of 64 bit values
much faster than something like quicksort.
In any case, the speed of these two sorts for things like tables of
values
is so much faster than things like quick sort, it makes an investment
in the
time and memory space practical.
I once used an optimize distribution sort for a mail list of about
500 names.
It ran several hundred times faster than quicksort of the same list.
I'd places
optimizations in it to deal with empty fields in the names. I don't
recall
exactly how it worked but the fellow that was using that mail list was
happy.
Dwight
