REXX Tips & Tricks, Version 2.80


Inf-HTML [About][Toc][Index] 0.9b (c) 1995 Peter Childs


Shellsort routine - 1 -


SHELL-Sortroutine from Steve Pitts (see EMail Addresses) 
Captured from a message in a public CompuServe Forum 


 
/* Routine SHELLSORT.                                                 */
/*                                                                    */
/* This REXX subroutine can be used to perform a generic sort. It has */
/* been written in a generic fashion to make it as easy as possible   */
/* to plug it into the EXEC of your choice. The algorithm used is the */
/* fastest non-recursive one that I know of for lists in random       */
/* sequence, but if you've got one that's faster, then I challenge    */
/* you to produce an equivalent of this routine using your algorithm. */
/*                                                                    */
/* Before calling this procedure you need to have set up two arrays,  */
/* key. and ind., containing, respectively, the key field for         */
/* comparison purposes, and an index (or pointer) to each element.    */
/*                                                                    */
/* The subroutine takes two numeric arguments representing the first  */
/* and last elements to be sorted, and returns ind. as a pointer list */
/* in ascending order. To change it to sort into descending order all */
/* you need do is change the line that compares key.kind to tempdat   */
/* so that the test is inverted (ie. > becomes <). Alternatively you  */
/* could process the index in reverse order (see below).              */
/*                                                                    */
/* Thus if you had done a CP QUERY RDR ALL into a variable RDRLIST.   */
/* you would code the following to sort it into file name order:      */
/*                                                                    */
/* do i=1 to rdrlist.0                                                */
/*    key.i=substr(rdrlist.i,54,8)                                    */
/*    ind.i=i                                                         */
/* end                                                                */
/*                                                                    */
/* call shellsort 2,rdrlist.0                                         */
/*                                                                    */
/* Note that the first index is 2 because rdrlist.1 is a header line. */
/*                                                                    */
/* To print the list in sorted order you would then code:             */
/*                                                                    */
/* do i=1 to rdrlist.0                                                */
/*    rind=ind.i                                                      */
/*    say rdrlist.rind                                                */
/* end                                                                */
/*                                                                    */
/* Note the use of the pointer. Unfortunately it is not possible to   */
/* code rdrlist.(ind.i) to get the same effect in a single statement. */
/* To display items in descending order you simply reverse the loop,  */
/* do i=rdrlist.0 to 1 by -1, although this would display the header  */
/* at the end, in this instance!                                      */
/*                                                                    */
/**********************************************************************/
/*                                                                    */
/*  VER   TIME   DATE    BY   NARRATIVE                               */
/*  1.0  15:22 90/02/20 SJP - Original version. Generic sort routine  */
/*                            using Shell algorithm.                  */
/*  1.1  10:13 90/12/07 SJP - Added check for first element number    */
/*                            not being less than last element        */
/*                            number.                                 */
/*  1.2  09:49 92/02/19 SJP - Moved procedure statement for VM/ESA.   */
/*  1.3  10:51 93/08/27 SJP - Tidied up and corrected documentation.  */
/*                                                                    */
/**********************************************************************/
shellsort: PROCEDURE expose key. ind.
  trace o
              /* Check that there are at least two elements to sort   */
  parse arg low, high
  if low >= high then
    return

              /* Calculate an optimal initial gap size                */
  gap = 1
  do while gap < (high-low)+1
     gap = gap*3
  end

              /* Basically we sort the elements 'gap' elements        */
              /* apart, gradually reducing 'gap' until it is one,     */
              /* at which point the list will be fully sorted.        */
  do until gap = 1
     gap=gap/3
     do i=(gap+low) to high
        j=i
        tempind=ind.j
        tempdat=key.tempind
        k=j-gap
        kind=ind.k
        do while key.kind > tempdat
           ind.j=ind.k
           j=k
           k=j-gap
           if k < low then leave
           kind=ind.k
        end
        ind.j=tempind
     end
  end
RETURN

  

Inf-HTML End Run - Successful