20
Sat, Apr
5 New Articles

Rev Up RPG Sorts

RPG
Typography
  • Smaller Small Medium Big Bigger
  • Default Helvetica Segoe Georgia Times

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.


Giuseppe Costagliola is a programmer in Turin, Italy. You can reach him atThis email address is being protected from spambots. You need JavaScript enabled to view it.

BLOG COMMENTS POWERED BY DISQUS

LATEST COMMENTS

Support MC Press Online

$0.00 Raised:
$

Book Reviews

Resource Center

  • SB Profound WC 5536 Have you been wondering about Node.js? Our free Node.js Webinar Series takes you from total beginner to creating a fully-functional IBM i Node.js business application. You can find Part 1 here. In Part 2 of our free Node.js Webinar Series, Brian May teaches you the different tooling options available for writing code, debugging, and using Git for version control. Brian will briefly discuss the different tools available, and demonstrate his preferred setup for Node development on IBM i or any platform. Attend this webinar to learn:

  • SB Profound WP 5539More than ever, there is a demand for IT to deliver innovation. Your IBM i has been an essential part of your business operations for years. However, your organization may struggle to maintain the current system and implement new projects. The thousands of customers we've worked with and surveyed state that expectations regarding the digital footprint and vision of the company are not aligned with the current IT environment.

  • SB HelpSystems ROBOT Generic IBM announced the E1080 servers using the latest Power10 processor in September 2021. The most powerful processor from IBM to date, Power10 is designed to handle the demands of doing business in today’s high-tech atmosphere, including running cloud applications, supporting big data, and managing AI workloads. But what does Power10 mean for your data center? In this recorded webinar, IBMers Dan Sundt and Dylan Boday join IBM Power Champion Tom Huntington for a discussion on why Power10 technology is the right strategic investment if you run IBM i, AIX, or Linux. In this action-packed hour, Tom will share trends from the IBM i and AIX user communities while Dan and Dylan dive into the tech specs for key hardware, including:

  • Magic MarkTRY the one package that solves all your document design and printing challenges on all your platforms. Produce bar code labels, electronic forms, ad hoc reports, and RFID tags – without programming! MarkMagic is the only document design and print solution that combines report writing, WYSIWYG label and forms design, and conditional printing in one integrated product. Make sure your data survives when catastrophe hits. Request your trial now!  Request Now.

  • SB HelpSystems ROBOT GenericForms of ransomware has been around for over 30 years, and with more and more organizations suffering attacks each year, it continues to endure. What has made ransomware such a durable threat and what is the best way to combat it? In order to prevent ransomware, organizations must first understand how it works.

  • SB HelpSystems ROBOT GenericIT security is a top priority for businesses around the world, but most IBM i pros don’t know where to begin—and most cybersecurity experts don’t know IBM i. In this session, Robin Tatam explores the business impact of lax IBM i security, the top vulnerabilities putting IBM i at risk, and the steps you can take to protect your organization. If you’re looking to avoid unexpected downtime or corrupted data, you don’t want to miss this session.

  • SB HelpSystems ROBOT GenericCan you trust all of your users all of the time? A typical end user receives 16 malicious emails each month, but only 17 percent of these phishing campaigns are reported to IT. Once an attack is underway, most organizations won’t discover the breach until six months later. A staggering amount of damage can occur in that time. Despite these risks, 93 percent of organizations are leaving their IBM i systems vulnerable to cybercrime. In this on-demand webinar, IBM i security experts Robin Tatam and Sandi Moore will reveal:

  • FORTRA Disaster protection is vital to every business. Yet, it often consists of patched together procedures that are prone to error. From automatic backups to data encryption to media management, Robot automates the routine (yet often complex) tasks of iSeries backup and recovery, saving you time and money and making the process safer and more reliable. Automate your backups with the Robot Backup and Recovery Solution. Key features include:

  • FORTRAManaging messages on your IBM i can be more than a full-time job if you have to do it manually. Messages need a response and resources must be monitored—often over multiple systems and across platforms. How can you be sure you won’t miss important system events? Automate your message center with the Robot Message Management Solution. Key features include:

  • FORTRAThe thought of printing, distributing, and storing iSeries reports manually may reduce you to tears. Paper and labor costs associated with report generation can spiral out of control. Mountains of paper threaten to swamp your files. Robot automates report bursting, distribution, bundling, and archiving, and offers secure, selective online report viewing. Manage your reports with the Robot Report Management Solution. Key features include:

  • FORTRAFor over 30 years, Robot has been a leader in systems management for IBM i. With batch job creation and scheduling at its core, the Robot Job Scheduling Solution reduces the opportunity for human error and helps you maintain service levels, automating even the biggest, most complex runbooks. Manage your job schedule with the Robot Job Scheduling Solution. Key features include:

  • LANSA Business users want new applications now. Market and regulatory pressures require faster application updates and delivery into production. Your IBM i developers may be approaching retirement, and you see no sure way to fill their positions with experienced developers. In addition, you may be caught between maintaining your existing applications and the uncertainty of moving to something new.

  • LANSAWhen it comes to creating your business applications, there are hundreds of coding platforms and programming languages to choose from. These options range from very complex traditional programming languages to Low-Code platforms where sometimes no traditional coding experience is needed. Download our whitepaper, The Power of Writing Code in a Low-Code Solution, and:

  • LANSASupply Chain is becoming increasingly complex and unpredictable. From raw materials for manufacturing to food supply chains, the journey from source to production to delivery to consumers is marred with inefficiencies, manual processes, shortages, recalls, counterfeits, and scandals. In this webinar, we discuss how:

  • The MC Resource Centers bring you the widest selection of white papers, trial software, and on-demand webcasts for you to choose from. >> Review the list of White Papers, Trial Software or On-Demand Webcast at the MC Press Resource Center. >> Add the items to yru Cart and complet he checkout process and submit

  • Profound Logic Have you been wondering about Node.js? Our free Node.js Webinar Series takes you from total beginner to creating a fully-functional IBM i Node.js business application.

  • SB Profound WC 5536Join us for this hour-long webcast that will explore:

  • Fortra IT managers hoping to find new IBM i talent are discovering that the pool of experienced RPG programmers and operators or administrators with intimate knowledge of the operating system and the applications that run on it is small. This begs the question: How will you manage the platform that supports such a big part of your business? This guide offers strategies and software suggestions to help you plan IT staffing and resources and smooth the transition after your AS/400 talent retires. Read on to learn: