Softpanorama (slightly skeptical) Open Source Software Educational Society

May the source be with you, but remember the KISS principle ;-)

Radix Sort

Radix sort is classified by Knuth as "sorting by distribution" (See Vol 3, 5.2.5. Sorting by distribution. P.168). It is the most efficient sorting method for alphanumeric keys on modern computers provided that the keys are not too long. Floating number sorting is also possible, but you need to do some tricks here. Radix sort is stable, very fast and generally is an excellent algorithm on modern computers that usually have large memory. 

The idea of radix soft is very similar to the idea of hashing algorithms. You compute the final position of the record for each key. If there is already a record(s) with this keys you place the record after them (overflow area). You  do not compare the key with other keys at all. It is similar to the method by which people lookup up a person's number in a telephone book: first the first letter is checked, then the second, etc.  Knuth illustrated it on the example of sorting of a card deck:

These methods were used to sort punched cards for many years, long before electronic computers existed. The same approach can be adapted computer programming, and it is generally known as "bucket sorting", "radix sorting," or "digital sorting," because it is based on the digits on the keys,

Suppose we want to sort a 52-card deck of playing cards. We may define

A < 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K

as an ordering of the face values, and for the suits we may define:

 c(lubs) <  d(iamonds) < h(earts) < s(pades).

One card is to precede another if either (i) its suit is less than the other suit, or (ii) its suit equals the other suit but its face value is less. (This is a particular case of lexographic ordering between ordered pairs of objects; see exersize 5-2). Thus

cA < c2 < ... < cK  < dA <d2... <dK  <hA ... <hK <sA...<sK

We could sort the cards by any of the methods already discussed. Card players often use a technique somewhat analogous to the idea behind radix players often use a technique somewhat analogous to the idea behind radix exchange. First they divide the cards into four piles, according to suit, then they fiddle with each individual pile until everything is in order.

But there is a faster way to do the trick! First deal the cards face up into 13 piles, one for each face value. Then collect these piles by putting the aceson the bottom, the 2s face up on top of them, then the 3s, etc., finally putting the kings (face up) on the top. Turn the deck face down and deal again this time into four piles for the four suits. (Again you turn the cards face up as you deal dial. Putting the resulting piles together, with clubs on the bottom, then diamonds, hearts, and spades, you'' get the deck in perfect order.

In radix-sorting algorithms, all keys should be the same size or padded to the same size. The algorithm treats the keys as numbers represented as numbers of the base R (for example base 8 means that bytes are used as key constituents, base 16 means that halfwords are used, etc). It is most efficient for short keys for example classic sorting case of sorting 4 byte integers is perfect for radix sort. 

to program radix sort the operation "extract the ith digit from a key"  should be available. The designers of  all modern languages, including C, C++, and Java recognized that direct manipulation of bits is often useful and provided corresponding operations.

Availability of byte and half-word operation in hardware can speed radix sort, but is not absolutly necessary.

There are two approaches to radix sorting.

• MSD most-significant-digit radixsort methods examine the digits in the keys in a left-to-right order, working with the most significant digits first. MSD radix sorts partition the file according to the leading digits of the keys, then recursively apply the same method to the subfiles. You can think of quicksort as a method somewhat similar to radix sort with base 2. 

• LSS -- least-significant-digit ) radix sorts. The second class of radix-sorting methods examine the digits in the keys in a right-to-left order, working with the least significant digits first.

Recommended Links

***** Radix Sort Revisited

***** An Efficient Radix Sort

***** A New Efficient Radix Sort - Andersson, Nilsson (ResearchIndex)

**** Radix Sort

**** Parallel Radix Sort

**** Bucket and radix sorting

****  Radix sort - Wikipedia, the free encyclopedia

*** Radix sorting (http://www.math.grin.edu/~stone/courses/fundamentals/radix-sorting.html)

**** Radix Sort Tutorial
 

Radix Sort

Radix Sort

*** Data Structures and Algorithms Radix Sort

Radix Sort

[Robert McIvor is a retired research chemist. He has been programming the Macintosh since 1984, and has developed programs for teaching and parsing Loglan®. Loglan is a constructed speakable language, capable of expressing the full range of human experience, yet whose sound stream and grammar are completely unambiguous The written language and potentially the spoken also are machine parsible.1]

Introduction

Prograph™ has been briefly described in MacTutor, March 1990. Now that a compiler to produce stand-alone applications is available, I decided to compare the performance with a C implementation. As a first experience, I attempted to convert the radix sort algorithm I described elsewhere2 to Prograph.

The sort time of the C version of the radix algorithm is linear in n, the number of records, in contrast to most currently used sorts, which are proportional to n log n. Unlike other algorithms, the time is also directly proportional to the length of the sort key; i.e. it takes as long to process 1000 10-byte keys, as to process 10000 1-byte keys. The previously published version sorted 20,000 bytes/sec. on an SE-30. An improved version sorts 88,235 bytes/sec. The C code for unbelievers is provided on this month’s source disk, along with Prograph implementations.

Adapting Radix Sort to the Memory Hierarchy - Rahman, Raman (ResearchIndex)

Presentations

• Microsoft PowerPoint - RadixSort

Implementations  

• Top-down radix sort

Last modified: February 28, 2008