Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #23949

som probabilistic sorts

Show all headers | View raw

Inspired by the recent flurry of sorting algorithms, I devised some of
my own, all probabilistic and pretty simple, but still a surprising
amount of of code.  All code plus some scaffolding at
<http://www.complang.tuwien.ac.at/forth/programs/badsort.fs>

The first one:

require random.fs
\ provides random ( n -- 0..n-1 )

: sorted? ( addr u -- f )
    assert( dup 1 u> )
    1- cells over + swap do
        i @ i cell+ @ u> if
            unloop false exit then
    1 cells +loop
    true ;

: exchange ( addr1 addr2 -- )
    over @ over @ >r swap ! r> swap ! ;

: badsort { addr u -- }
    u 2 u< if
        2drop exit then \ ensure assertion in sorted?
    begin
        addr u sorted? 0= while
            addr u random th addr u random th exchange
            1 steps +!
            \ addr u printarray cr
    repeat ;

That's pretty slow, because the swaps are completely undirected.

By having a directed exchange and otherwise the same algorithm we can
improve this a lot:

: maybe-exchange ( addr1 addr2 -- )
    2dup u<= >r over @ over @ 2dup u<= r> = if
        2drop 2drop
    else
        >r swap ! r> swap !
    then ;

: so-so-sort { addr u -- }
    u 2 u< if
        2drop exit then \ ensure assertion in sorted?
    begin
        addr u sorted? 0= while
            addr u random th addr u random th maybe-exchange
            1 steps +!
            \ addr u printarray cr
    repeat ;

Now checking the array after every step costs quite a bit, so we
perform a number of directed exchange step between checks in the next
version:

: mediocre-sort { addr u -- }
    u 2 u< if
        2drop exit then \ ensure assertion in sorted?
    begin
        addr u sorted? 0= while
            u 8 * 0 do \ only check for sortedness now and then
                addr u random th addr u random th maybe-exchange
                1 steps +!
            loop 
            \ addr u printarray cr
    repeat ;

One could run maybe u^(3/2) MAYBE-EXCHANGEs (without any checking) to
get the array into a mostly-sorted state, then use something like
bubble sort or insertion sort to take care of the rest, and maybe get
better performance than these quadratic sort algorithms would have
achieved by themselves (something like the Shellsort idea).

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2013: http://www.euroforth.org/ef13/

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

Thread

som probabilistic sorts anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-06-26 16:17 +0000
  Re: som probabilistic sorts mhx@iae.nl - 2013-06-26 11:59 -0700

csiph-web