Re: Baden's recursive Quicksort revisited

From	"Ed" <invalid@invalid.com>
Newsgroups	comp.lang.forth
Subject	Re: Baden's recursive Quicksort revisited
Date	2013-10-18 15:37 +1000
Organization	Aioe.org NNTP Server
Message-ID	<l3qe22$9ke$1@speranza.aioe.org> (permalink)
References	<l36drg$t8$1@speranza.aioe.org> <5257cc10$0$15874$e4fe514c@news2.news.xs4all.nl> <l3csvg$3b0$1@speranza.aioe.org> <525e4f7d$0$15946$e4fe514c@news2.news.xs4all.nl>

Show all headers | View raw

Hans Bezemer wrote:
> "Ed" <invalid@invalid.com> Wrote in message:
> ...
> > Lastly I note some implementations of Wil's code posted online comment
> > out the statement:
> >
> >     2OVER 2OVER  - + > IF  2SWAP  THEN
> Yes, interesting thingy. But in field tests I found a speedup of
>  5-10% in 4tH. So, I left it to the programmer to decide what he
>  wants - using [PRAGMA].

BTW the code above which tests partition length and puts the shorter
on TOS can fail too.  It's a trade-off between speed/accuracy.

\  2over 2over - + > if 2swap then ( Baden, fast)
\  2over 2over - -rot - < if 2swap then ( good, slower)
\  2dup swap - >r 2over swap - r> u< if 2swap then ( best, slowest)

Any of the above would do as the routine is non-critical.  The second
one gets it right for all but exceptional cases (when a partition is
greater than half the address range).

Back to comp.lang.forth | Previous | Next — Previous in thread | Find similar | Unroll thread

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