+ Search
Add Entry AlertManage Folder Edit Entry Add page to http://del.icio.us/
Did You Find This Entry Useful?

6 of 15 people (40%) answered Yes
Recently 5 of 10 people (50%) answered Yes


What is radix sort

Feb 18th, 2007 05:15
Articles Directory, Suvojeet Pal, http://americanahost.com

A radix sort is an algorithm, a procedure, which can rearrange integer 
representations based on the processing of individual digits in such a 
way that the integer representations are eventually in either 
ascending or descending order. Integer representations can be used to 
represent things such as strings of characters (names of people, 
places, things, the words and characters that you are reading now, 
dates, etc.) and specially formatted floating point numbers as well as 
integers. So, anything which can be represented as an ordered sequence 
of integer representations can be rearranged to be in order by a radix 
sort. Most digital computers internally represent all of their data as 
electronic representations of binary numbers, so processing the digits 
of integer representations by groups of binary digit representations 
is most convenient. Two classifications of radix sorts are least 
significant digit (LSD) radix sorts and most significant digit (MSD) 
radix sorts. LSD radix sorts process the integer representations 
starting from the least significant digit and move the processing 
towards the most significant digit. MSD radix sorts process the 
integer representations starting from the most significant digit and 
move the processing towards the least significant digit. The integer 
representations that are processed by sorting algorithms are often 
called, "keys," which can exist all by themselves or be associated 
with other data. LSD radix sorts typically use the following sorting 
order: short keys come before longer keys, and keys of the same length 
are sorted lexicographically. This coincides with the normal order of 
integer representations, such as the sequence 1, 2, 3, 4, 5, 6, 7, 8, 
9, 10. MSD radix sorts use lexicographic order, which is suitable for 
sorting strings, such as words, or fixed-length integer 
representations. A sequence such as b, c, d, e, f, g, h, i, j, ba 
would be lexicographically sorted as b, ba, c, d, e, f, g, h, i, j. If 
lexicographic ordering is used to sort variable-length integer 
representations, then the representations of the numbers from 1 to 10 
would be output as 1, 10, 2, 3, 4, 5, 6, 7, 8, 9, as if the shorter 
keys were left-justified and padded on the right with blank characters 
to make the shorter keys as long as the longest key for the purpose of 
determining sorted order.
source: http://en.wikipedia.org/wiki/Radix_sort
i hope that help.