Path: utzoo!utgpu!jarvis.csri.toronto.edu!clyde.concordia.ca!uunet!willett!ForthNet
From: ForthNet@willett.UUCP (ForthNet articles from GEnie)
Newsgroups: comp.lang.forth
Subject: All Sorts of Sorts
Message-ID: <427.UUL1.3#5129@willett.UUCP>
Date: 9 Feb 90 00:41:52 GMT
Organization: Latest link in the ForthNet chain.  (Pgh, PA)
Lines: 103


 Date: 02-07-90 (17:50)              Number: 2871 (Echo)
   To: ALL                           Refer#: NONE
 From: ZAFAR ESSAK                     Read: (N/A)
 Subj: LEARN TO SORT                 Status: PUBLIC MESSAGE

 \ SORTS.FLY     Part 2 - Different Sort Methods 

 (( 
 The BUBBLE SORT compares the first element with the second element. 
 If necessary they are exchanged.  Then the second element is compared 
 with the third, etc.  Thus, the largest element will be moved to the 
 end of the list while most others only move down one position.  The 
 result is an unsorted list with a length one less than the previous 
 list.  The list size is decreased and the sort repeated until the 
 list size is zero. 

 Consecutive sorts will preserve the effects of prior sorts. 

 )) 

 : BUBBLE ( --) 
     1 DATA.MAX# @ 1- 
     ?DO I 0 
         ?DO I DUP 1+ 
             0 data.buf 1 data.buf 
             2OVER 2OVER 
             ROT DATA@ SWAP DATA@ SORT? 0> 
                 IF EXCHANGE ELSE 2DROP THEN 
             LOOP 
     -1 +LOOP ; 

 (( 
 The SHELL SORT is similar to the bubble sort except that instead of 
 comparing each element with the next element it is compared with an 
 element further down the list.  However, it does not preserve the 
 effects of prior sorts when consecutive sorts are performed. 
 When the sort is started the gap between the numbers being compared 
 is set equal to half the length of the list.  When the routine can 
 go through the list without trading the gap is halved and the 
 routine repeated.  When the gap equals zero the sort is finished. 

 )) 

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

 : SHL ( --) 
     gap @ 0= IF EXIT THEN 
     gap @ 2/ gap ! 
     1 DATA.MAX# @ 1- gap @ - 
         ?DO traded OFF I 0 
             ?DO I DUP gap @ + 
                 0 data.buf 1 data.buf 
                 2OVER 2OVER 
                 ROT DATA@ SWAP DATA@ SORT? 0> 
                     IF EXCHANGE traded ON   ELSE 2DROP  THEN 
                 LOOP 
             traded @ 0= ?LEAVE 
         -1 +LOOP 
     RECURSE ; 

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

 (( 
 The QWIK SORT is much faster than either the Bubble or Shell sorts. 
 Furthermore, it does not preserve the effects of prior sorts when 
 consecutive sorts are performed. 

 The middle element of the unsorted list is used to divide the list 
 into two piles.  The highest pile is in turn divided into two and 
 this process repeated until the top pile is a collection of sorted 
 elements.  Then attention is focused on the preceeding pile to sort 
 it.  This is repeated until all the "piles" have been sorted. 

 )) 

 : QSORT| ( l,r--)                   \ QWIK SORT by Dan Phillips 
     2DUP < NOT IF 2DROP EXIT THEN 
     2DUP + 2/ 0 data.buf SWAP DATA@ 
     2DUP 
         BEGIN SWAP 
             BEGIN 1 data.buf OVER DATA@ 
                   1 data.buf 0 data.buf SORT? 0< 
             WHILE 1+ 
             REPEAT SWAP 
                 BEGIN 1 data.buf OVER DATA@ 
                       1 data.buf 0 data.buf SORT? 0> 
                 WHILE 1- 
                 REPEAT 2DUP > NOT 
                     IF 2DUP EXCHANGE SWAP 1+ SWAP 1- 
                     THEN 2DUP > 
         UNTIL -ROT SWAP 
     RECURSE RECURSE ; 

 : QSORT ( --) 0 DATA.MAX# @ 1-  QSORT| ;           \ Part 3... 
 ---
  * 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'