Sorting is an essential part of computing because most business data processing relies on sorting and searching. For this reason, sorting is one of the most studied problems in computer science and why many sorting algorithms exist, each with its own merits. Since the days of the S/38, RPG programmers have been able to use the SORTA operation to sort arrays. (For more information about SORTA, see “SORTA Grows Up” on the Midrange Computing Web site at www.midrangecomputing. com/mc.) But even with recent enhancements, SORTA is not always an effective way to sort large amounts of data.

I would like to outline some of the techniques that can be used on AS/400 with RPG and ILE to sort arrays, multiple-occurrence data structures, and user spaces. I will describe three well-known sorting algorithms: bubble sort, quicksort, and heap sort. I will present two versions of quicksort: a “homemade” version and IBM’s C-language implementation. I will also briefly discuss the theory of each algorithm. For a thorough discussion of these and other theories, consult the books listed in the references at the end of this article. The exact mathematical analysis of the efficiency of each algorithm is not my objective, but you will get an idea of the great differences in performance for each algorithm by examining the comparative CPU usage in the accompanying tables. I will also give you the code to measure the performance of each implementation, as well as a simple program to try all the sorts described in the article. But before I explain how to call these procedures into practice, I will examine some popular sorting algorithms.

Bubble Sort

This sort is the right one to start with because it is an algorithm that uses less code and is the easiest to understand. Using this sort, each neighbouring couple of elements is compared and switched if they are not in order, so the lowest keys bubble up to the top of the array one at a time. This sorting routine is stable, meaning that the elements with the same key remain in their original order and are not swapped by some random exchange process.

Unfortunately this is also the slowest of all the sorts, but consider it for short arrays since the cost of writing more code isn’t worth the processing time saved. Its runtime is said to be of O(N2) in the worst case. The O( ) notation, called “big O notation”, is an indication of an algorithm’s efficiency in proportion to the number of inputs. For example, if sort time is O(N), you can expect sort time to triple if you change the number of elements

of an array to three times the current value. O(N2) means that the execution time increases according to the square of the number of elements in the array. Therefore, the bubble sort is unsuitable for medium or large arrays.

Quicksort

Invented by C.A.R. Hoare in 1960, quicksort has become very popular. This technique uses a divide and conquer algorithm that consists of partitioning the array into members that will be sorted in turn. The algorithm is naturally expressed recursively (i.e., quicksort calls itself to sort its members). Quicksort is available on the AS/400 as the ANSI C standard library function, qsort, which is callable now from any RPG or COBOL ILE program. Quicksort has long been considered the fastest sort a programmer can use, and it has an excellent average time of O(N * log2(N)) * K where K is a very small constant. (I found that 0.000005 makes the actual timings closest to the theoretical timings). It is not necessary to know exactly what log2(N) is, but it is important to note that the function log2(N) grows much more slowly than N itself. For instance when N=1, log2(N) is quite close to N’s value; but as N grows to 1024, log2(N) only grows to 10.

Unfortunately quicksort performs poorly if the data is already in sequence or if the keys are almost equal. When this happens, which is not uncommon, quicksort makes N recursive calls in order to complete sorting the whole array. This results in an O(N2) run time—exactly like poor bubble sort! In the downloadable source code that accompanies this article, I have placed a non-recursive quicksort version that uses two additional small arrays to keep track of the members that have not yet been sorted. When dealing with medium to large arrays, or with arrays that have most of the keys equal, this version performs slightly better than the C qsort function. But if you are looking for speed at any cost, take a look at the bibliography and you will find other optimizations of quicksort, each one with its advantages and disadvantages.

Heap Sort

This algorithm, invented by J.W.J. Williams, also has a performance standard of O(N * log2(N)) * K but generally runs slower than quicksort. I’ve found that the constant K that still satisfies the performance formula is 0.0000135, almost three times the constant value for quicksort. However, heap sort has the advantage that even in the worst case it still runs in O(N * log2(N)). To understand how this algorithm works, you must learn about trees and heaps, which are thoroughly explained in the books referenced at the end of this article.

Give Your Sort a Big Push

The four sorting procedures—the three I wrote and a prototype for IBM’s Quicksort—are ready to use and have been packaged into a unique service program. You can download the source code for these procedures and accompanying test programs from www.midrangecomputing.com/mc. Each procedure can be directly called from ILE RPG programs to sort arrays, multiple-occurrence data structures, or user-spaces. Each array or structure can have any number of elements, and each element can be up to 32,767 bytes in length. Sorting can run in both ascending and descending sequence, based on a key that can be either part of the array element or the whole element itself. You only need to decide which algorithm you will use.

As I’ve just said, your choice should not depend only on volumes of data to sort since arrays already sequenced will heavily degrade the performance of some algorithms. There are situations in which we generally know in advance if data has already been partially sorted or has most of the keys equal. For example, if you sort postings by currency code, you would expect to find many of the postings in the local currency. Or, if you extract all the spooled files into a user space, and you want to reorder the list by spool date, many entries could have the same spool date. Both of these examples would cause the

sorting process to run very slowly if the wrong algorithm were used. In any case, you can test all four routines, measure the performance, and decide accordingly.

My three procedures—bubble, heap, and quicksort—have the same parameter interface, so they are fully interchangeable. Notice that the first parameter is a pointer that addresses the first element of the array, so if you are sorting multiple structures, remember to use the OCCUR opcode to set the pointer address to the first occurrence. If you are sorting user spaces, retrieve the pointer with the QUSPTRUS API and set the pointer to the start of the list section using the offset available from the header information. The remaining parameters specify the number of elements to sort and the width of each element—the sort sequence and the key location as offset within the array element and its length.

The second implementation of quicksort combines the power of C and the flexibility of RPG in the ILE environment. Because any C standard library function is available to all ILE languages, you will also find a sort procedure that uses the standard ASCII qsort function. This function needs an additional parameter for the procedure pointer to the compare function that allows you to write a more sophisticated comparison, like on non- contiguous keys.

The compare argument is a pointer to a function you must supply which qsort calls one or more times during the sort. The compare function can be directly included in your main program or put in a service program. This function, called directly by the C qsort, receives two pointers. The first (key@) addresses the key, and the second (element@) addresses the current element of the array. You can define two variables, key and element, based on these pointers with the maximum allowed length for a string and then make a comparison of two substrings using the key offset and its length.

The function must compare the key and the element and return a negative value if the key is less than the element, a positive value if the key is greater than the element, or a zero if the two are equal. If sorting should occur in reverse order, just reverse the returned integer value.

Put Sort Procedures to Work

All three sort procedures, the compare function needed for C qsort, and the CPU usage analyzer (a useful procedure for measuring performance, and not only for sorting) have been packaged into one service program; but you can also directly include or /COPY the code into your program if you prefer. The examples that follow refer to the implementation with a service program.

The snippet of code in Figures 1 and 2 should give you an idea of how to integrate these sort routines into an RPG program. Figure 1 applies to the three sort routines I developed. Figure 2 is for the C qsort.

The process consists of only four steps. First, declare the variables that are common to all the sort routines. Notice that they are imported from the sort module. Second, include the appropriate sort prototype. The sort prototype is hard-coded in the example, but you may want to keep prototypes in source members of their own and use /COPY to bring them in to your source code.

Third, initialize the variables that control the sort: the sequence (A or D), the key offset within the element, and its length. These fields have been put outside the procedure parameters to provide a common interface to the homemade routines and C qsort; however, you can make separate service programs for homemade routines and include these fields in the procedure parameter.

Finally, run the sort routine with the appropriate CALLP command. The CALLP parameters are the array or the structure (for structures remember to start at the first occurrence), the actual number of elements to be sorted, the array’s element length, and the compare function, which is used only by C qsort. Sorting data directly into a user space is similar in concept. See Figure 3 for an example.

Compare Performances

The service program includes the RTVCPU procedure, which will help you choose the routine that runs faster. Call RTVCPU twice, before and after sorting, and calculate the CPU used as the difference of the figures returned by the function. Figure 4 shows average actual CPU times for sorting a multiple-occurrence data structure up to 32,000 elements. Elements were loaded from a customer master file and sorted upon unordered fields (name) and fields with many equal keys (country). The shaded area in the table indicates the best algorithm for that volume and type of data.

As you can see, bubble sort can be used only for small arrays (especially if the original sequence of equal elements should be preserved), while for larger arrays the choice is between heap sort and quicksort, depending on the expected values of the sort keys. You can also see that sorting 32,000 elements with many equal keys by using heap sort takes less than five seconds, while C qsort takes four minutes (50 times). The same table, however, with very different keys and not pre-ordered, can be sorted with C qsort in one third the time of the heap sort. Reported timings are in CPU seconds; actual runtime depends on how many other jobs are running during the sort.

Figure 5 shows the typical order of execution for each algorithm and the expected timings for sorting a similar table of up to 1.024 million records. At the present time, RPG IV limits the maximum number of elements in arrays to 32,767, while a user space is only

limited to its global size. This timing again refers to unsorted tables. When working with tables with many equal key values, the heap sort performs much better than quicksort, which performs like bubble sort. From the table in Figure 5, you can easily extend both the heap sort and qsort columns for arrays with equal keys and see that the expected run time for sorting a table of 1.024 million elements would be approximately 276 CPU seconds with heap sort and 35 days with bubble sort or quicksort!

Try It Yourself

The TSTSORT demo program allows you to display a source file member list and dynamically sort it using any of the four procedures. You can compare the advantages and disadvantages of each algorithm. Sorting occurs directly into the user space. Even if member list API takes a significant time to retrieve members from large source files, once it’s loaded, space sorting with the best-suited procedure is done quickly.

REFERENCES AND RELATED MATERIALS

• An Introduction to Programming—A Structured Approach. R. Conway and D. Gries.
1978.

•ILE C for AS/400 Run-Time Library Reference V4R4 (SC41-5607, CD-ROM QB3AT500)

• Introduction to Algorithms. Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Cambridge, Massachusetts: MIT Press, 1990

• MI Library Reference (SC09-2418, CD-ROM QBJADR00)

• The Art of Computer Programming, Volume 3, Second Edition: Sorting and Searching. Donald E. Knut. Reading, Massachusetts: Addison-Wesley Longman, Inc., 1998

* declare common variables
d ArSrtSeq s 1a import
d ArKeyOff s 10i 0 import

d ArKeyLng s 10i 0 import

* prototype the selected sort routine
d SortAr PR extproc(‘SORTU’)
d Ar@ * value
d ArTotElem 10i 0 const
d ArLngElem 10i 0 const

* define the sort sequence and key

* specification (location and length)
c eval ArSrtSeq = ‘A’
c eval ArKeyOff = 11
c eval ArKeyLng = 10

* sort the multiple structure using home-made procedure
c 1 occur MStructure
c callp SortAr(%addr(MStructure):
c ActualEntries:
c %len(MStructure))

* declare common variables
d ArSrtSeq s 1a import
d ArKeyOff s 10i 0 import
d ArKeyLng s 10i 0 import

** C/C++ quicksort
d SortQC PR extproc(‘qsort’)
d ar@ * value
d ArTotElem 10u 0 value
d ArLngElem 10u 0 value
d ArCompare * value procptr

** Compare function
d COMPARE PR 10i 0 extproc(‘COMPARE’)
d key@ * value
d element@ * value
d prc s * procptr dinz(%paddr(‘COMPARE’))

* define the sort sequence and key

* specification (location and length)
c eval ArSrtSeq = ‘A’
c eval ArKeyOff = 11
c eval ArKeyLng = 10

** sort the multiple structure using C qsort
c 1 occur MStructure
c callp SortQC(%addr(MStructure):
c ActualEntries:
c %len(MStructure):
c prc)

* declare sort common variables and prototype procedures as above

* include the space definitions (available from QSYSINC/QRPGLESRC)

* and the list entry definition:
d*d* User space header
d*d Header ds based(header@)
d* Offset List Data
d qusold 125 128B 0
d* Number List Entries
d qusnbrle 133 136B 0
d* Size Each Entry
d qussee 137 140B 0

d*d* list entry
d*d ListE ds based(liste@)
d FieldOne 10
d FieldTwo 10
d FieldThree 10

* retrieve the address of the user space header
c call 'QUSPTRUS'
c parm spcname

Figure 1: This code illustrates how RPG programs access the sort procedures.

Figure 2: Using the C quicksort requires slightly different prototypes and parameter list.

c parm header@

* define the sequence and keys, and position the pointer

* pointer to the beginning of the list section
c eval ArSrtSeq = 'A'
c eval ArKeyOff = 11
c eval ArKeyLng = 10
c eval liste@ = header@ + qusold

c** sort the list (using home-made procedures)
c callp SortAr(liste@: qusnbrle: qussee)

c** sort the list (using C qsort)
c callp SortQC(liste@: qusnbrle: qussee: prc)

** at this point, extract the sorted entries from the user

** space as usual

Figure 3: Here’s an example of sorting data in a user space.

Number Heap Sort Quick Sort C Qsort Bubble of Rcds Unsorted Part srt Unsorted Part srt Unsorted Part srt Sort

50 0.006 0.004 0.003 0.005 0.002 0.002 0.008 100 0.009 0.006 0.004 0.011 0.003 0.007 0.022 500 0.059 0.047 0.022 0.105 0.021 0.046 0.718 1,000 0.134 0.112 0.048 0.298 0.043 0.138 2.783 2,000 0.292 0.235 0.108 0.777 0.106 1.005 11.630 4,000 0.646 0.489 0.235 3.225 0.226 5.550 46.352 8,000 1.406 1.078 0.504 12.847 0.518 22.764 186.728 12,000 2.194 1.666 0.732 27.453 0.796 44.256 16,000 2.990 2.247 1.075 48.655 1.154 73.010 32,000 6.494 4.927 2.602 202.389 2.541 268.084

Number Heap Sort Quick Sort Bubble Sort of Rcds Actual Expected Actual Expected Actual Expected 50 0.006 0.004 0.003 0.001 0.008 0.007 500 0.059 0.061 0.022 0.022 0.718 0.725 1,000 0.134 0.135 0.048 0.050 2.783 2.900 2,000 0.292 0.296 0.108 0.110 11.630 11.600 4,000 0.646 0.646 0.235 0.239 46.352 46.400 8,000 1.406 1.400 0.504 0.519 186.728 185.600 16,000 2.990 3.017 1.075 1.117 742.400 32,000 6.494 6.465 2.602 2.395 2,970 49 min 64,000 13.794 5.109 11,878 3 hours 128,000 29.317 10.858 47,514 13 hours 256,000 62.090 22.996 190,054 2 days 512,000 131.092 48.552 760,218 9 days 1,024,000 276.007 102.225 3,040,870 35 days

O() N*Log2(N)*0.000013 N*Log2(N)*0.000005 N2 * 0.000003

Figure 4: These are actual sort times, illustrating the appropriateness of each sort algorithm.

Figure 5: These are projected sort times for increasing numbers of elements to be sorted.