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

Groups > comp.lang.postscript > #1595

Re: YA quicksort function

Show all headers | 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

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

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