Standard C++ Library User Guide and Tutorial

Click on the banner to return to the user guide home page.

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.