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: <425.UUL1.3#5129@willett.UUCP>
Date: 9 Feb 90 00:41:44 GMT
Organization: Latest link in the ForthNet chain.  (Pgh, PA)
Lines: 48


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

 This is not meant to detract from Ian Green's Modula-2 discussions 
 where he has been discussing SORTS, but rather may shed more light on 
 the topic; at least from a novice sorter's viewpoint. 

 I would also like to apologize at the outset for the lack of references 
 to the results of the Forth Sort contest that was held on GEnie.  I 
 would appreciate a note from anyone who recalls the name(s) of the 
 files that pertain to that contest.  I have looked over the various 
 files related to sorts on the BCFB and found the descriptions of sorts 
 by Norm Arnold in SORT_WIN.ZIP most helpful. 

 To begin using and understanding SORTS I needed a generalized approach 
 that would allow applying the SORT methods to a variety of data 
 elements.  This requires the use of a few variables and deferred 
 execution words.  Vector variables were chosen for the deferred words. 
 There is an obvious performance penalty in using a generalized approach 
 such as this but I felt it would give me an opportunity to understand 
 the various SORT methods as well as allow experimentation on different 
 data elements. 

 The most striking, though simple, find was discovered through 
 experimenting with consecutive SORTS.  Data elements containing several 
 fields were first sorted on one field and then sorted on a second 
 field.  Of the three sorts tried (BUBBLE, SHELL, and QWIK) only the 
 BUBBLE Sort preserved the ordering of the first sort within the second 
 sort.  Unfortunately, the BUBBLE sort is by far the slowest of the 
 three, taking five times longer than the QWIK sort and twice as long as 
 the SHELL sort. 

 The next few messages contain the Forth code used.  This is essentially 
 Forth-83 Standard which has implications in the DO...+LOOP where a 
 negative integer is used.  A simple example of an array sort was used 
 to initially test the functioning of the sorts.  This is illustrated 
 with the code but requires a RANDOM number generator, several of which 
 are available on the board. 
 ---
  * 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'