AI Horizon: Intelligence and Reason in Computers
Introduction Home Essays Resources Contact Info
Essays
  Basic CS
General AI
Chess AI
Go AI

Resources
  Source Code
AI Tips and Tricks
Books
Links

Other
  Code Journal
Site Updates

An Affiliate of Cprogramming.com
 

Radix Sort, Part 1
(Up to Basic Computer Science : Lists and Arrays : Sorting Algorithms)

[Part 1] [Part 2]

Radix Sort is a clever and intuitive little sorting algorithm. Radix Sort puts the elements in order by comparing the digits of the numbers. I will explain with an example.

Consider the following 9 numbers:

493   812   715   710   195   437   582   340   385

We should start sorting by comparing and ordering the one's digits:

Digit Sublist
0   340 710
1  
2   812 582
3   493
4  
5   715 195 385
6  
7   437
8  
9  

Notice that the numbers were added onto the list in the order that they were found, which is why the numbers appear to be unsorted in each of the sublists above. Now, we gather the sublists (in order from the 0 sublist to the 9 sublist) into the main list again:

340   710   812   582   493   715   195   385   437

Note: The order in which we divide and reassemble the list is extremely important, as this is one of the foundations of this algorithm.

Now, the sublists are created again, this time based on the ten's digit:

Digit Sublist
0  
1   710 812 715
2  
3   437
4   340
5  
6  
7  
8   582 385
9   493 195

Now the sublists are gathered in order from 0 to 9:

710   812   715   437   340   582   385   493   195

Finally, the sublists are created according to the hundred's digit:

Digit Sublist
0  
1   195
2  
3   340 385
4   437 493
5   582
6  
7   710 715
8   812
9  

At last, the list is gathered up again:

195   340   385   437   493   582   710   715   812

And now we have a fully sorted array! Radix Sort is very simple, and a computer can do it fast. When it is programmed properly, Radix Sort is in fact one of the fastest sorting algorithms for numbers or strings of letters.

Radix Sort Part 2: Disadvantages

All content is written and published by the people at or affiliated with AI Horizon <http://www.aihorizon.com/>.
Send any comments and suggestions to comments@aihorizon.com.

Please report any errors to webmaster@aihorizon.com.