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 /* corrected RXT&T v3.40 */
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