9.3.1 Writing a Sort Function

Earlier in this chapter we presented the lotto script for picking x random numbers out of a series of y numbers. The script that we showed did not sort the list of numbers that were selected. In this section, we develop a sort function that sorts the elements of an array.

We define a function that takes two arguments, the name of the array and the number of elements in the array. This function can be called this way:

sort(sortedpick, NUM)

The function definition lists the two arguments and three local variables used in the function.

# sort numbers in ascending order
function sort(ARRAY, ELEMENTS,   temp, i, j) {
        for (i = 2; i <= ELEMENTS; ++i) {
                for (j = i; ARRAY[j-1] > ARRAY[j]; --j) {
                        temp = ARRAY[j]
                        ARRAY[j] = ARRAY[j-1]
                        ARRAY[j-1] = temp
                }
        }
        return
}

The body of the function implements an insertion sort. This sorting algorithm is very simple. We loop through each element of the array and compare it to the value preceding it. If the first element is greater than the second, the first and second elements are swapped. To actually swap the values, we use a temporary variable to hold a copy of the value while we overwrite the original. The loop continues swapping adjacent elements until all are in order. At the end of the function, we use the return statement to simply return control.[6] The function does not need to pass the array back to the main routine because the array itself is changed and it can be accessed directly.

[6] In this case, the return is not strictly necessary; "falling off the end" of the function would have the same effect. Since functions can have return values, it's a good idea to always use a return statement, even when you are not returning a value. This helps make your programs more readable.

Here's proof positive:

$ lotto 7 35


Pick 7 of 35
6 7 17 19 24 29 35

In fact, many of the scripts that we developed in this chapter could be turned into functions. For instance, if we only had the original, 1987, version of nawk, we might want to write our own tolower() and toupper() functions.

The value of writing the sort() function in a general fashion is that you can easily reuse it. To demonstrate this, we'll take the above sort function and use it to sort student grades. In the following script, we read all of the student grades into an array and then call sort() to put the grades in ascending order.

# grade.sort.awk -- script for sorting student grades
# input: student name followed by a series of grades

# sort function -- sort numbers in ascending order
function sort(ARRAY, ELEMENTS, 	temp, i, j) {
	for (i = 2; i <= ELEMENTS; ++i) 
		for (j = i; ARRAY[j-1] > ARRAY[j]; --j) { 
			temp = ARRAY[j]
			ARRAY[j] = ARRAY[j-1]
			ARRAY[j-1] = temp
	}
	return 
}

# main routine
{ 
# loop through fields 2 through NF and assign values to
# array named grades
for (i = 2; i <= NF; ++i)
	grades[i-1] = $i 

# call sort function to sort elements

sort(grades, NF-1)

# print student name
printf("%s: ", $1)

# output loop
for (j = 1; j <= NF-1; ++j)
	printf("%d ", grades[j])
printf("\n")
}

Note that the sort routine is identical to the previous version. In this example, once we've sorted the grades we simply output them:

$ awk -f grade.sort.awk grades.test


mona: 70 70 77 83 85 89
john: 78 85 88 91 92 94
andrea: 85 89 90 90 94 95
jasper: 80 82 84 84 88 92
dunce: 60 60 61 62 64 80
ellis: 89 90 92 96 96 98

However, you could, for instance, delete the first element of the sort array if you wanted to average the student grades after dropping the lowest grade.

As another exercise, you could write a version of the sort function that takes a third argument indicating an ascending or descending sort.

9.3.2 Maintaining a Function Library

You might want to put a useful function in its own file and store it in a central directory. Awk permits multiple uses of the -f option to specify more than one program file.[7] For instance, we could have written the previous example such that the sort function was placed in a separate file from the main program grade.awk . The following command specifies both program files:

[7] The SunOS 4.1.x version of nawk does not support multiple script files. This feature was not in the original 1987 version of nawk either. It was added in 1989 and is now part of POSIX awk.

$ awk -f grade.awk -f /usr/local/share/awk/sort.awk grades.test

This command assumes that grade.awk is in the working directory and that the sort function is defined in sort.awk in the directory /usr/local/share/awk .

NOTE: You cannot put a script on the command line and also use the -f option to specify a filename for a script.

Remember to document functions clearly so that you will understand how they work when you want to reuse them.

9.3.3 Another Sorted Example

Lenny, our production editor, is back with another request.

Dale:

The last section of each Xlib manpage is called "Related Commands"
(that is the argument of a .SH) and it's followed by a list of commands
(often 10 or 20) that are now in random order.  It'd be more
useful and professional if they were alphabetized.  Currently, commands
are separated by a comma after each one except the last, which has a
period.

The question is: could awk alphabetize these lists?  We're talking
about a couple of hundred manpages.  Again, don't bother if this is a
bigger job than it seems to someone who doesn't know what's involved.

Best to you and yours, 

Lenny

To see what he is talking about, a simplified version of an Xlib manpage is shown below:

.SH "Name"
XSubImage  -  create a subimage from part of an image.
.
.
.
.SH "Related Commands"
XDestroyImage, XPutImage, XGetImage, 
XCreateImage, XGetSubImage, XAddPixel, 
XPutPixel, XGetPixel, ImageByteOrder.

You can see that the names of related commands appear on several lines following the heading. You can also see that they are in no particular order.

To sort the list of related commands is actually fairly simple, given that we've already covered sorting. The structure of the program is somewhat interesting, as we must read several lines after matching the "Related Commands" heading.

Looking at the input, it is obvious that the list of related commands is the last section in the file. All other lines except these we want to print as is. The key is to match all lines from the heading "Related Commands" to the end of the file. Our script can consist of four rules, that match:

1. The "Related Commands" heading

2. The lines following that heading

3. All other lines

4. After all lines have been read (END )

Most of the "action" takes place in the END procedure. That's where we sort and output the list of commands. Here's the script:

# sorter.awk -- sort list of related commands
# requires sort.awk as function in separate file
BEGIN { relcmds = 0 } 

#1 Match related commands; enable flag x 
/\.SH "Related Commands"/ {
	print
	relcmds = 1
	next
}

#2 Apply to lines following "Related Commands" 
(relcmds == 1) {
	commandList = commandList $0
}

#3 Print all other lines, as is.
(relcmds == 0) { print }

#4 now sort and output list of commands 
END {
# remove leading spaces and final period.
	gsub(/, */, ",", commandList)
	gsub(/\. *$/, "", commandList)
# split list into array
	sizeOfArray = split(commandList, comArray, ",")
# sort
	sort(comArray, sizeOfArray)
# output elements
	for (i = 1; i < sizeOfArray; i++)
		printf("%s,\n", comArray[i])  
	printf("%s.\n", comArray[i])
}

Once the "Related Commands" heading is matched, we print that line and then set a flag, the variable relcmds , which indicates that subsequent input lines are to be collected.[8] The second procedure actually collects each line into the variable commandList . The third procedure is executed for all other lines, simply printing them.

[8] The getline function introduced in the next chapter provides a simpler way to control reading input lines.

When all lines of input have been read, the END procedure is executed, and we know that our list of commands is complete. Before splitting up the commands into fields, we remove any number of spaces following a comma. Next we remove the final period and any trailing spaces. Finally, we create the array comArray using the split() function. We pass this array as an argument to the sort() function, and then we print the sorted values.

This program generates the following output:

$ awk -f sorter.awk test


.SH "Name"
XSubImage  -  create a subimage from part of an image.
.SH "Related Commands"
ImageByteOrder,
XAddPixel,
XCreateImage,
XDestroyImage,
XGetImage,
XGetPixel,
XGetSubImage,
XPutImage,
XPutPixel.

Once again, the virtue of calling a function to do the sort versus writing or copying the code to do the same task is that the function is a module that's been tested previously and has a standard interface. That is, you know that it works and you know how it works. When you come upon the same sort code in the awk version, which uses different variable names, you have to scan it to verify that it works the same way as other versions. Even if you were to copy the lines into another program, you would have to make changes to accommodate the new circumstances. With a function, all you need to know is what kind of arguments it expects and their calling sequence. Using a function reduces the chance for error by reducing the complexity of the problem that you are solving.

Because this script presumes that the sort() function exists in a separate file, it must be invoked using the multiple -f options:

$ awk -f sort.awk -f sorter.awk test

where the sort() function is defined in the file sort.awk .