Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.forth > #26439
| From | "Ed" <invalid@invalid.com> |
|---|---|
| Newsgroups | comp.lang.forth |
| Subject | Re: Baden's recursive Quicksort revisited |
| Date | 2013-10-13 12:27 +1000 |
| Organization | Aioe.org NNTP Server |
| Message-ID | <l3csvg$3b0$1@speranza.aioe.org> (permalink) |
| References | <l36drg$t8$1@speranza.aioe.org> <5257cc10$0$15874$e4fe514c@news2.news.xs4all.nl> |
Hans Bezemer wrote:
> Ed wrote:
>
> > \ The Recursive Quicksort "qsort.txt" on Wil Baden's website is
> > \ buggy (try it!).
>
> Ed, this code (in some form or another) is still very much in use with
> KForth, SwitftForth and 4tH. I never found any problem with it, but if you
> have an example me and I assume the maintainers of other compilers would
> very much like to know.
> ...
The statement in Wil's "qsort.txt" which causes it to fail (dramatically) is:
1 CELLS INVERT CONSTANT -CELL
Perhaps it was a simple oversight and what he intended was:
1 CELLS 1- INVERT CONSTANT -CELL
The other problems in "qsort.txt" relate to using signed operators on addresses
and unsigned numbers which typically affects 16-bit Forths sooner. Curiously
his original FD code (essentially what I posted) was mostly correct.
It highlights the difficulty (folly?) of writing "portable code". 32-bit Forth users
are more likely to make such errors because the bugs rarely bite *them*.
Another bug is the use of 2/ . This is wrong for the reasons given above but
curiously still works. The only ill-effect seems to be a few more iterations.
Ideally 2/ should be replaced with U2/ (or 1 RSHIFT if you don't have it).
Lastly I note some implementations of Wil's code posted online comment
out the statement:
2OVER 2OVER - + > IF 2SWAP THEN
In the aforementioned FD article Wil specifically warns against this. A quick
test I did indicates including the line can reduce data stack usage by almost half.
Again, unlikely to affect 32-bit Forths.
Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Baden's recursive Quicksort revisited "Ed" <invalid@invalid.com> - 2013-10-11 01:31 +1000
Re: Baden's recursive Quicksort revisited albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-10-10 15:49 +0000
Re: Baden's recursive Quicksort revisited anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-10-10 17:42 +0000
Re: Baden's recursive Quicksort revisited "Ed" <invalid@invalid.com> - 2013-10-18 15:16 +1000
Re: Baden's recursive Quicksort revisited Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-10-20 03:18 -0500
Re: Baden's recursive Quicksort revisited anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-10-21 16:33 +0000
Re: Baden's recursive Quicksort revisited Hans Bezemer <the.beez.speaks@gmail.com> - 2013-10-11 12:03 +0200
Re: Baden's recursive Quicksort revisited Alex McDonald <blog@rivadpm.com> - 2013-10-11 05:15 -0700
Re: Baden's recursive Quicksort revisited "Ed" <invalid@invalid.com> - 2013-10-13 12:25 +1000
Re: Baden's recursive Quicksort revisited "Alex McDonald" <blog@rivadpm.com> - 2013-10-13 08:59 +0100
Re: Baden's recursive Quicksort revisited Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-10-13 04:50 -0500
Comparing addresses (was: Baden's recursive Quicksort revisited) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-10-15 15:17 +0000
Re: Comparing addresses Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-10-15 14:34 -0500
Re: Comparing addresses anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-10-16 14:15 +0000
Re: Comparing addresses Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-10-20 02:51 -0500
Re: Comparing addresses anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-10-22 11:18 +0000
Re: Comparing addresses albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-10-22 13:26 +0000
Re: Comparing addresses anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-10-22 13:39 +0000
Re: Comparing addresses Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-10-22 13:30 -0500
Re: Comparing addresses anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-10-23 07:48 +0000
Re: Comparing addresses m.a.m.hendrix@tue.nl - 2013-10-23 23:49 -0700
Re: Comparing addresses anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-10-24 09:01 +0000
Re: Baden's recursive Quicksort revisited albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-10-13 12:06 +0000
Re: Baden's recursive Quicksort revisited all2001@spambog.com (Wolfgang Allinger) - 2013-10-13 11:42 -0400
Re: Baden's recursive Quicksort revisited "Ed" <invalid@invalid.com> - 2013-10-13 12:27 +1000
Re: Baden's recursive Quicksort revisited Hans Bezemer <the.beez.speaks@gmail.com> - 2013-10-16 10:35 +0200
Re: Baden's recursive Quicksort revisited Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-10-16 03:51 -0500
Re: Baden's recursive Quicksort revisited albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-10-16 10:50 +0000
Re: Baden's recursive Quicksort revisited anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-10-16 14:27 +0000
Re: Baden's recursive Quicksort revisited "Ed" <invalid@invalid.com> - 2013-10-18 15:37 +1000
csiph-web