Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!wuarchive!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!aplcen!uunet!willett!ForthNet
From: ForthNet@willett.UUCP (ForthNet articles from GEnie)
Newsgroups: comp.lang.forth
Subject: All Sorts of Sorts
Message-ID: <439.UUL1.3#5129@willett.UUCP>
Date: 11 Feb 90 03:23:00 GMT
Organization: Latest link in the ForthNet chain.  (Pgh, PA)
Lines: 110


 Date: 02-09-90 (16:04)              Number: 2877 (Echo)
   To: IAN GREEN                     Refer#: 2874
 From: ZAFAR ESSAK                     Read: NO
 Subj: LEARN TO SORT                 Status: PUBLIC MESSAGE

 Ian, 

     Your assumption that the tests I did were on random lists is 
 absolutely correct.  Your comments on partly ordered lists resulting in 
 admirable performances for the BUBBLE Sort got me to review the code. 
 The following contains a minor revision to exit as soon as no 
 exchanging of items is required. 

 \ The BUBBLE Sort 

 VARIABLE gap ( --adr) 
 VARIABLE traded ( --adr)    \ flag to indicate if elements exchanged 

 : pair.sort ( n1,n2--)            \ : pair.sort ( n1,n2--) 
     0 data.buf 1 data.buf         \   2DUP  1 data.buf SWAP DATA@ 
     2OVER 2OVER                   \         0 data.buf SWAP DATA@ 
     ROT DATA@ SWAP DATA@ SORT? 0> \   0 data.buf 1 data.buf SORT? 0> 
         IF EXCHANGE traded ON     \         IF EXCHANGE traded ON 
         ELSE 2DROP THEN ;         \         ELSE 2DROP THEN ; 

 : BUB ( --) 
     1 DATA.MAX# @ gap @ - 
         ?DO traded OFF I 0 
             ?DO I DUP gap @ + pair.sort LOOP 
             traded @ 0= ?LEAVE 
         -1 +LOOP ; 

 : BUBBLE ( --) 1 gap ! BUB ; 

 \ The SHELL Sort 

 : SHL ( --) 
     gap @ DUP 0= IF DROP EXIT THEN 
         2/ gap ! BUB RECURSE ; 

 : SHELL.SORT ( --) DATA.MAX# @ gap ! SHL ; 

 This provides for some better factoring as well as performance. 

 I have also gone through an early (1986) issue of Forth Dimensions and 
 have added the BATCHER'S Sort to the set.  Here it is. 

 (( 
 BATCHER'S SORT is slightly slower, but more robust than Qwik sort 
 and has consistent sorting times.  Depending on the input data, in 
 some cases Batcher's sort may be faster than Qwik sort. 

 Unfortunately, it too does not preserve the effects of prior sorts 
 when consecutive sorts are performed. 

 Batcher's sort consists of three nested loops.  The innermost loop 
 compares pairs of keys that are completely independent.  Thus 
 parallel computing could be applied for very fast sorting. 

 From Forth Dimensions Nov/Dec 86 p 39 by John Konopka 

 The names of the variables were chosen to be consistent with the 
 description of the algorithm given by Knuth. 

 )) 

 CREATE 2** ( --adr) 
        1 ,    2 ,    4 ,     8 ,    16 ,    32 ,    64 ,  128 , 
      256 ,  512 , 1024 ,  2048 ,  4096 ,  8192 , 16384 , 

 : 2**N ( n -- 2**n ) 2* 2** + @ ; 

 VARIABLE DD ( --adr)    VARIABLE NN ( --adr)    VARIABLE PP ( --adr) 
 VARIABLE QQ ( --adr)    VARIABLE RR ( --adr)    VARIABLE TT ( --adr) 

 : SELECT-T ( --) 
     NN @ 15 0 DO DUP I 2**N <= IF DROP I LEAVE THEN LOOP 
     1- 14 MIN TT ! ; 

 : INNER-LOOP ( --) 
     NN @ DD @ - 0 
         ?DO I PP @ AND RR @ = 
             IF I DUP DD @ + pair.sort 
             THEN LOOP ; 

 : Q-TEST ( --) 
     QQ @ PP @ <> 
         IF  QQ @ PP @ - DD ! 
             QQ @ 2/ QQ ! 
             PP @ RR ! 0 
         THEN ; 

 : QRD-SET ( --) TT @ 2**N QQ !  RR OFF  PP @ DD ! ; 

 : BATCHER ( --) 
     DATA.MAX# @ NN ! 
     SELECT-T TT @ 2**N PP ! 
     BEGIN QRD-SET QQ @ 
         BEGIN INNER-LOOP Q-TEST 
         UNTIL PP @ 2/ DUP PP ! 0= 
     UNTIL ; 

 ---
  * Via Qwikmail 2.01

 NET/Mail : British Columbia Forth Board - Burnaby BC - (604)434-5886   
-----
This message came from GEnie via willett through a semi-automated process.
Report problems to: 'uunet!willett!dwp' or 'willett!dwp@gateway.sei.cmu.edu'