Sorting routine

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

On Aug 29, 4:03*pm, Frank <fjru...@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

Frank 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.

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?

Frank fjrusso@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

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

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


On Aug 29, 5:26*pm, John Passaniti <n...@JapanIsShinto.com> wrote:
> Frank 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.
>
> 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?

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

On Aug 29, 5:23*pm, "roger.l...@gmail.com" <roger.l...@gmail.com>
wrote:
> On Aug 29, 4:03*pm, Frank <fjru...@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

Frank <fjrusso@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...%3A1qayaf_i0fw

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

On Aug 29, 3:06*pm, Thomas Pornin <por...@bolet.org> wrote:
> According to Frank *<fjru...@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/Cate...ing_Algorithms

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

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

Review and additional Forth implementations welcome.

Ian

On Aug 29, 2:42*pm, Frank <fjru...@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...hInsertionSort

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

Ian

On Aug 29, 4:03*pm, Frank <fjru...@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

Thank you one and all, you pointed me in a good direction.

Frank