The radix sort algorithm is a good illustration of how ** list**s and

NOTE: The complete radix sort program is in the file radix.cpp.

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 are examined, the list must be sorted.

Table 11 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.
## Table 11 -- Sequence of values in each bucket during radix sort

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. The value of the variable `divisor` indicates which digit is currently being examined. A boolean flag is used to determine when execution should halt. Each time the `while` loop is executed, a ** vector** of

void radixSort(list<unsigned int> & values) { bool flag = true; int divisor = 1; while (flag) { vector< deque<unsigned int> > buckets(10); flag = false; for_each(values.begin(), values.end(), copyIntoBuckets(...)); accumulate(buckets.begin(), buckets.end(), values.begin(), listCopy); divisor *= 10; } }

The use of the function `accumulate()` here is slightly unusual. The *scalar* value being constructed is the ** list** itself. The initial value for the accumulation is the iterator denoting the beginning of the

list<unsigned int>::iterator listCopy(list<unsigned int>::iterator c, deque<unsigned int> & lst) { // copy list back into original list, returning end return copy(lst.begin(), lst.end(), c); }

The only difficulty remaining is defining the function `copyIntoBuckets()`. The problem here is that the function must take as its argument only the element being inserted, but it must also have access to the three values `buckets`, `divisor`, and `flag`. In languages that permit functions to be defined within other functions, the solution is to define `copyIntoBuckets()` as a local function within the `while` loop. But C++ has no such facilities. Instead, we must create a class definition, which can be initialized with references to the appropriate values. The parenthesis operator for this class is then used as the function for the `for_each()` invocation in the radix sort program.

class copyIntoBuckets { public: copyIntoBuckets (int d, vector< deque<unsigned int> > & b, bool & f) : divisor(d), buckets(b), flag(f) {} int divisor; vector<deque<unsigned int> > & buckets; bool & flag; void operator () (unsigned int v) { int index = (v / divisor) % 10; // flag is set to true if any bucket // other than zeroth is used if (index) flag = true; buckets[index].push_back(v); } };

©Copyright 1998, Rogue Wave Software, Inc.

Send mail to report errors or comment on the documentation.

OEM Release, June 1998