Dr. Dirk Terrell is an astronomer at the University of Florida specializing in interacting binary stars. His hobbies include cave diving, martial arts, painting and writing OS/2 software such as HTML Wizard.
Blast Back! Send a private message directly to Dr. Dirk Terrell with your thoughts:
Go to a Printer Friendly version of this page
Summary: Learn how to sort a stem variable without loosing track of its tails
A few months back we took a look at some sorting algorithms and implemented REXX code to perform them. (See the December 1997 and January 1998 issues.) The code that we developed would sort a single set of values stored in a stem variable. In some situations however, your needs are a little more complicated. One case is the need to sort a set of values but have several other stem variables "follow" the one that is sorted. For example, let's say you have a stem variable Weight. with values of several people's weights. But you also have stem variables Name. and Height. Obviously if you sort the Weight. values, the values in Name. and Height. are no longer going to be in the correct order. We need Name. and Height. to "follow" the values of Weight. when they are rearranged. This month we will modify our original heap sort code to include this capability.
First off, let's create some data to work with by setting up stem variables to hold the names, weights, and heights:
N=5 Name.0=5 Name.1="Chris" Name.2="Bill" Name.3="Tom" Name.4="Fred" Name.5="Henry" Weight.0=5 Weight.1=155 Weight.2=180 Weight.3=220 Weight.4=125 Weight.5=175 Height.0=5 Height.1=6.0 Height.2=5.96 Height.3=5.75 Height.4=6.2 Height.5=6.1In the old heapsort code we required that the stem variable stem. be populated with the values to be sorted. Let's make things a bit more convenient by allowing any stem variable to be sorted. Let's also allow any number of arbitrary stem variables to follow the sorted one. To do this, we can use the Expose option on the Procedure instruction in our sorting routine. Recall that Expose allows the subroutine to see only the specified variables from elsewhere in the program. All other variables will be hidden from your routine. (Which keeps you from accidentally modifying a variable.) Normally, you would explicitly list the variables that you want to see:
HeapSort: Procedure Expose Name. Height. Weight.But this would greatly reduce the flexibility of our routine by requiring a change to the expose option each time we used the routine. It would be better if we could specify the names of the exposed variables in the contents of another variable. And you can indeed do that by placing the name of the variable in parehtheses like this:
HeapSort: Procedure Expose (Arrays)In this case, the contents of the variable Arrays contains the names of the stem variables that we will operate on. For our example with stems with name, weight, and height, it might be set like this:
Arrays = "Name. Weight. Height."This option makes it easy to tell our sort routine which stems to perform the sorting on. For our program, let's establish the convention that the first stem in the list is the one whose values will determine the sorting and the others will be the ones that follow it. So, if we want to sort by weight, we would set up the Arrays variable as
Arrays = "Weight. Name. Height."Now, how do we modify the old code which used the variable stem. for the data? Using the REXX Interpret instruction, we can do this pretty easily. What we will do is copy the contents of the specified sort variable into stem. as stem.1, stem.2, stem.2 and so on. The stem.0 variable will contain the number of values to be sorted. We will also add another level to the stem. for the values of the arrays that are following the sort array. For example, stem.1.2 would contain the first value of the second stem variable passed, i.e., Name.1 in the example above. To set up stem. we use this code:
Interpret "NItems="||Word(Arrays,1)||"0" /* Copy the original stems to temporary ones */ Do i=0 to NItems Interpret "Stem.i="||Word(Arrays,1)||i Do j=2 to NArrays Interpret "Stem.i.j="||Word(Arrays,j)||i end /* do */ end /* do */The Interpret instruction tells REXX to create the string that follows it and execute it as if it were written originally in the program. Take a look at the first line of the setup code above:
Interpret "NItems="||Word(Arrays,1)||"0"This line tells REXX to take the first word of Arrays (which is "Weight." in our example), concatenate a zero onto it and add the string "NItems=" to the front of it. Thus the string that results is
NItems=Weight.0REXX then executes that instruction, setting the variable NItems to the value of Weight.0. Then for each data value, we create a string that sets the value in stem. to the value in the array that we have been asked to sort. We also set up the values for the arrays that will follow the sorted array.
At this point we have the variable stem. populated with the data that we want to sort, so our old sort code will correctly sort the data. What we have to add is the code to make the other arrays follow changes in the array we are sorting. In each place where we change the contents of the sorted stem, we have to make the corresponding change in the other stems. For example, in the old code we have the following code to swap the contents of two entries in the stem:
t = stem.1 stem.1 = stem.n stem.n = tIn the new code we add loops to make those swaps in the other arrays:
t = stem.1 Do i=2 to NArrays t.i=Stem.1.i end /* do */ stem.1 = stem.n Do i=2 to NArrays Stem.1.i=Stem.n.i end /* do */ stem.n = t Do i=2 to NArrays Stem.n.i=t.i end /* do */Once all of those changes are made, all we have to do is copy the contents of stem. back to the original arrays before we return to the program that called our sorting routine. This involves simply reversing what we did at the beginning of the sorting routine:
/* Re-order the original stems */ Do i=0 to NItems Interpret Word(Arrays,1)||i||"="||"Stem.i" Do j=2 to NArrays Interpret Word(Arrays,j)||i||"="||"Stem.i.j" end /* do */ end /* do */That's all there is to it. We now have a generalized heap sort routine that enables us to sort any stem variable and to have any number of other stem variables follow the sorted array. I think you might find this routine quite useful. The way we have written it makes it very easy to drop into existing code. All you have to do is set Arrays properly and then call the heap sort routine. Upon return from the call, the specified stem variables will be sorted correctly. The example code (.CMD, 4K) for this issue creates some data and then sorts them (try modifying the Arrays variable to sort on height or name.)
|Copyright © 1998 - Falcon Networking||ISSN 1203-5696||November 1, 1998|