Re: YA quicksort function

Path	csiph.com!usenet.pasdenom.info!aioe.org!news.mb-net.net!news.babsi.de!open-news-network.org!news2.open-news-network.org!.POSTED!not-for-mail
From	Mark Carroll <mtbc@bcs.org>
Newsgroups	comp.lang.postscript
Subject	Re: YA quicksort function
Date	Sun, 25 Aug 2013 09:50:28 +0100
Organization	none
Lines	111
Message-ID	<87li3qf92j.fsf@ixod.org> (permalink)
References	<a0e13204-b665-45bb-92c8-724d97d82482@googlegroups.com>
NNTP-Posting-Host	82-71-47-217.dsl.in-addr.zen.co.uk
Mime-Version	1.0
Content-Type	text/plain; charset=us-ascii
X-Trace	news2.open-news-network.org 1377420628 23019 82.71.47.217 (25 Aug 2013 08:50:28 GMT)
X-Complaints-To	abuse@open-news-network.org
NNTP-Posting-Date	Sun, 25 Aug 2013 08:50:28 +0000 (UTC)
User-Agent	Gnus/5.13 (Gnus v5.13) Emacs/23.4 (gnu/linux)
Cancel-Lock	sha1:TgA7S1q/bLhlk9wcBQrvQzdx6dA=
Xref	csiph.com comp.lang.postscript:1595

Show key headers only | View raw

For what it's worth, years ago I wrote a mergesort,

/sortarray
{
  8 dict begin
  
  /lessthan exch def

  dup length 0 gt
  {
    /mergetwo
    {
      /first exch def
      /second exch def
      /result first length second length add array def
      
      /firstat 0 def
      /secondat 0 def     

      0 1 result length 1 sub
      {
        /resultat exch def

        firstat first length eq
        {
          result resultat second secondat second length secondat sub getinterval putinterval
          exit
        }
        if

        secondat second length eq
        {
          result resultat first firstat first length firstat sub getinterval putinterval
          exit
        }
        if

        /firstelement first firstat get def
        /secondelement second secondat get def
        
        firstelement secondelement lessthan
        {
          result resultat firstelement put
          /firstat firstat 1 add def
        }
        {
          result resultat secondelement put
          /secondat secondat 1 add def
        }
        ifelse
      }
      for

      result
    } def
    
    /mergeall
    {
      dup length 1 eq
      {
        0 get
      }
      {
        /previous exch def
        
        previous length 2 mod 0 eq
        {
          /next previous length 2 idiv array def
          /nextat 0 def

          0
        }
        {
          /next previous length 2 idiv 1 add array def
          /nextat 1 def

          next 0 previous 0 get put

          1
        }
        ifelse

        2 previous length 2 sub
        {
          dup 1 add previous exch get exch previous exch get mergetwo
          next nextat 3 -1 roll put
          /nextat nextat 1 add def
        }
        for

        next mergeall
      }
      ifelse
    } def
    
    [ exch { 1 array dup 3 1 roll 0 3 -1 roll put } forall ] mergeall
  }
  if

  end
} bind def

I'm not going to claim that it is all that great, and it badly needs
comments, but it works.

GS>[ (one) (two) (three) (four) (five) (six) ] { lt } sortarray ==
[(five) (four) (one) (six) (three) (two)]
GS>[ 1 2 9 8 7 4 5 6 3 ] { gt } sortarray ==     
[9 8 7 6 5 4 3 2 1]

-- Mark

Thread

YA quicksort function luser- -droog <mijoryx@yahoo.com> - 2013-08-25 00:05 -0700
  Re: YA quicksort function Mark Carroll <mtbc@bcs.org> - 2013-08-25 09:50 +0100
  Re: YA quicksort function Scott Hemphill <hemphill@hemphills.net> - 2013-08-25 21:54 -0400
    Re: YA quicksort function luser- -droog <mijoryx@yahoo.com> - 2013-08-25 21:57 -0700
  Re: YA quicksort function luser- -droog <mijoryx@yahoo.com> - 2013-08-26 00:45 -0700
  Re: YA quicksort function luser- -droog <mijoryx@yahoo.com> - 2013-09-03 22:51 -0700
    Re: YA quicksort function luser- -droog <mijoryx@yahoo.com> - 2013-09-03 23:47 -0700
  Re: YA quicksort function jdaw1 <jdawiseman@gmail.com> - 2014-03-31 06:40 -0700
  Re: YA quicksort function luser- -droog <mijoryx@yahoo.com> - 2014-04-06 21:51 -0700

csiph-web