Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!cs.utexas.edu!uunet!willett!ForthNet
From: ForthNet@willett.UUCP (ForthNet articles from GEnie)
Newsgroups: comp.lang.forth
Subject: All Sorts of Sorts
Message-ID: <480.UUL1.3#5129@willett.UUCP>
Date: 16 Feb 90 02:35:51 GMT
Organization: Latest link in the ForthNet chain.  (Pgh, PA)
Lines: 71


 Date: 02-13-90 (14:57)              Number: 2901 (Echo)
   To: ZAFAR ESSAK                   Refer#: 2898
 From: STEVE PALINCSAR                 Read: NO
 Subj: SELECTION SORT                Status: PUBLIC MESSAGE

 To quote from Knuth (The Art of Computer Programming, vol. 3, 
 Sorting and Searching), p. 139:
 .
 "5.2.3  Sorting by Selection
 .
 An important famly of sorting techniques is based on the idea 
 of repeated selection.  The simplest selection method is 
 perhaps the following:
     i) Find the smallest key; transfer the corresponding 
 record to the output area; then replace the key by the value 
 "" (which is assumed to be higher than any actual key).
     ii) Repeat step (i).  This time the second smallest key 
 will be selected, since the smallest key has been replaced by 
 .
     iii) Continue repeating step (i) until N records have 
 been selected.
 .
 The above method involves N - 1 comparisons...  There is an 
 obvious way to improve upon the situation, avoiding the use 
 of : we can take the selcted value and move it into its 
 proper position by exchanging it with the record currently 
 occupying that position.  Then we need not consider that 
 position again in future selections.  This idea yields our 
 first selection sorting algorithm."
 .
 [He goes on to describe Algorithm S (Straight selection sort) 
 which I won't quote.]  He goes on, on p. 141, to  say:
 .
 "It is interesting to compare Algorithm S to the bubble 
 sort...  Bubble sorting does less comparisons than straight 
 selection and it may seem to be preferable; but in fact 
 Program 5.2.2B [the bubble sort] is more than twice as slow 
 as Progam S!  Bubble sorting is handicapped by the fact that 
 it does so many exchanges, while straight selection involves 
 very little data movement."
 .
 To quote from Robert Sedgewick's _Algorithms_ (p. 95):  
 "Despite its simplicity, selection sort has quite an 
 important application: it is the method of choice for sorting 
 files with very large recoords and small keys."  Here'ss his 
 code (inn Pascal):
    procedure selection;
       var i,j,min,t: integer;
       begin
       for i:=1 to N do
          begin
          min:=i;
          for j:=1+1 to N do
             if a[j]<a[min] then min:=j;
          t:=a[min]; a[min]:=a[i]; a[i]:=t
          end;
       end;
 .
 Sedgewick describes the algorithm as follows:  "find the smallest
 element in the array and exchange it with the element in the first
 position, then find the second smallest element and exchange it with the 
 element in the second position, continuing in this way until the entire
 array is sorted. ...This is among the simplest of sorting methods, and
 it will work very well for small files.  Its running time is
 proportional  to N2.  ...Still selection sort is quite attractive for
 sorting (say) a thousand 1000-word records on one-word keys."
 (p. 95 for all the Sedgewick quotes & code)
-----
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'