HP Integrity NonStop H-Series - Manual (Page 80)

Click on the banner to return to the user guide home page.
©Copyright 1996 Rogue Wave Software
Example Program - Radix Sort
The radix sort algorithm is a good illustration of how lists and deques can be combined with
other containers. In the case of radix sort, a vector of deques is manipulated, much like a hash
table.
Obtaining the Sample Program
Radix sorting is a technique for ordering a list of positive integer values. The values are
successively ordered on digit positions, from right to left. This is accomplished by copying the
values into "buckets," where the index for the bucket is given by the position of the digit being
sorted. Once all digit positions have been examined, the list must be sorted.
The following table shows the sequences of values found in each bucket during the four steps
involved in sorting the list 624 852 426 987 269 146 415 301 730 78 593. During pass 1 the
ones place digits are ordered. During pass 2 the tens place digits are ordered, retaining the
relative positions of values set by the earlier pass. On pass 3 the hundreds place digits are
ordered, again retaining the previous relative ordering. After three passes the result is an
ordered list.
bucket pass 1 pass 2 pass 3
0 730 301 78
1 301 415 146
2 852 624, 426 269
3 593 730 301
4 624 146 415, 426
5 415 852 593
6 426, 146 269 624
7 987 78 730
8 78 987 852
9 269 593 987
The radix sorting algorithm is simple. A while loop is used to cycle through the various passes.