Sorting routine

Sorting routine

POPULAR GROUPS

more...

comp.lang.forth Profile…

Sorting routine

Author: Frank
Date: Aug 29, 2008 13:03

I am being lazy, thought I would ask if you could point me in the
direction of a sorting routine. I simply want to sort the elements in
an array. I have done it before just didn't want to start again from
scratch. Yes I did search the archives and nothing turned up.

Frank

61 Comments

Re: Sorting routine

Author: roger.levy
Date: Aug 29, 2008 14:23

On Aug 29, 4:03 pm, Frank yahoo.com> wrote:

> I am being lazy, thought I would ask if you could point me in the
> direction of a sorting routine. I simply want to sort the elements in
> an array. I have done it before just didn't want to start again from
> scratch. Yes I did search the archives and nothing turned up.
>
> Frank

I used this: http://en.literateprograms.org/Quicksort_(Forth) as a
starting point for a Z-sorting routine in my 3D scenegraph engine

no comments

Re: Sorting routine

Author: John Passaniti
Date: Aug 29, 2008 14:26

Frank wrote:

What kind of data is in each element of the array?

What kind of comparison is needed to know the order?

How many elements in the array?

How unsorted is the array (completely random, only a few entries out of
order, unknown)?

How often do you need to sort (just once when you start, whenever you
get new data, periodically at some rate)?

Do you know why I'm asking you these questions?

no comments

Re: Sorting routine

Author: C. G. Montgomery
Date: Aug 29, 2008 14:38

Frank fjrusso@yahoo.com wrote:

Algorithm 15 in the Forth Scientific Library is a shell sort for floating
point arrays, which could easily be adapted to arrays of other types.
http://www.taygeta.com/fsl/library/shellsrt.seq

If a shell sort is suitable for your problem.

regards cgm

no comments

Re: Sorting routine

Author: Frank
Date: Aug 29, 2008 14:42

Thank you John for reminding me...Yes I know why you are asking. I am
a scientific-engineer and the more info I have the better I can answer
a question.

The data is numeric, completely random. It needs to be sorted any time
the list grows. The list starts at ~ 260 and can grow to well no
limit. The array is dynamic and increases in size as it needs. At the
moment it has 350 of 512 elements occupied. Imagine the list is your
vocabulary in a hash form it grows as you do.

Frank

Show full article (1.27Kb)

no comments

Re: Sorting routine

Author: Frank
Date: Aug 29, 2008 14:45

Thanks for the link but it failed:

Quicksort (Forth
From LiteratePrograms
Jump to: navigation, search
There is currently no text in this page

Got another?

Frank

Show full article (0.74Kb)

1 Comment

Re: Sorting routine

Author: Thomas Pornin
Date: Aug 29, 2008 15:06

According to Frank yahoo.com>:

A good question might be: why isn't a sort word defined in
ANS Forth ? Even C has qsort().

--Thomas Pornin

no comments

Re: Sorting routine

Author: Marcel Hendrix
Date: Aug 29, 2008 15:06

Frank yahoo.com> writes Re: Sorting routine

> Thanks for the link but it failed:

> Quicksort (Forth
> From LiteratePrograms
> Jump to: navigation, search
> There is currently no text in this page

> Got another?

Quartus' page:

http://www.google.com/custom?num=100&hl=en&lr=&safe=off&client=pub-9448921371862747&cof...

The only one I know by heart:

: bubble ( -- )
#elements
1 DO A-list #elements I - CELLS
BOUNDS DO I 2@ > IF I 2@ I D! ENDIF CELL +LOOP
LOOP ;

But there is really too much to read about this on-line, even in Forth.

-marcel

no comments

Re: Sorting routine

Author: Ian Osgood
Date: Aug 29, 2008 15:20

On Aug 29, 3:06 pm, Thomas Pornin bolet.org> wrote:

> According to Frank yahoo.com>:
>

>> I am being lazy, thought I would ask if you could point me in the
>> direction of a sorting routine. I simply want to sort the elements in
>> an array. I have done it before just didn't want to start again from
>> scratch. Yes I did search the archives and nothing turned up.

>
> A good question might be: why isn't a sort word defined in
> ANS Forth ? Even C has qsort().
>
> --Thomas Pornin

For exactly the reasons that John Passaniti asked all those questions.
Each different answer leads you to a different sorting algorithm.

Also, some other sorting algorithm implementations can be found on
Rosetta Code in the "Sorting Algorithms" category.

http://www.rosettacode.org/wiki/Category:Sorting_Algorithms

http://www.rosettacode.org/wiki/Quicksort#Forth

http://www.rosettacode.org/wiki/Insertion_sort#Forth

Show full article (1.01Kb)

no comments

Re: Sorting routine

Author: Ian Osgood
Date: Aug 29, 2008 15:29

On Aug 29, 2:42 pm, Frank yahoo.com> wrote:

> Thank you John for reminding me...Yes I know why you are asking. I am
> a scientific-engineer and the more info I have the better I can answer
> a question.
>
> The data is numeric, completely random. It needs to be sorted any time
> the list grows. The list starts at ~ 260 and can grow to well no
> limit. The array is dynamic and increases in size as it needs. At the
> moment it has 350 of 512 elements occupied. Imagine the list is your
> vocabulary in a hash form it grows as you do.
>
> Frank

Sounds like a binary search plus insertion should be good enough to
maintain a sorted array:

http://wiki.forthfreak.net/index.cgi?BinarySearchInsertionSort

http://www.rosettacode.org/wiki/Binary_search#Forth

This is kind of a toy implementation. Use with a growable list of
strings (via ALLOCATE-FREE) is found in this application:

http://wiki.forthfreak.net/index.cgi?BoggleGame

Show full article (0.96Kb)

no comments

RELATED THREADS

Subject	Articles qty	Group
Re: Sorting order with sort()	1	macromedia.labs.spry_framework_for_ajax_prerelease ·