[Home]
[Edit this page]
[Recent Changes]
[Special Pages]
[Help]
RadixSort
It works on the same principle that most humans sort first. Given a list of names, One might first sort by the first letter, then the second letter, etc. Radix sort does this, only in reverse. First, a radix is chosen. For example, with a list of words, we might choose the letters of the words.
We have a list of linked lists, one for each of the possible letters in the word. We go through the list, starting at the last letter, and putting it in the appropriate list. We then collect them, in order, and put them back in the original list. They are now sorted by the last letter. This is repeated for each letter, until we get to the first letter. After collecting them the last time, the words will be in order.
One problem with this method is that it depends on a large radix. A small radix makes the length of the items to be sorted larger, thus making the length of the items more significant than the number. Larger radixes, however, require more memory. If a large amount of memory is available, this sort can be extremely fast.
[Edit this page] [Page history] [What links here] [Discuss this topic] [Printer Friendly]
RadixSort
(Computer science) Radix Sort
Is it possible to have a sort that runs in O(n) (linear) time? Yes, it is. Radix sort is the fastest sort in many situations, even faster than quick sort. On the negative side, it is sometimes limited in its applications, and it can require large amounts of memory at times.It works on the same principle that most humans sort first. Given a list of names, One might first sort by the first letter, then the second letter, etc. Radix sort does this, only in reverse. First, a radix is chosen. For example, with a list of words, we might choose the letters of the words.
We have a list of linked lists, one for each of the possible letters in the word. We go through the list, starting at the last letter, and putting it in the appropriate list. We then collect them, in order, and put them back in the original list. They are now sorted by the last letter. This is repeated for each letter, until we get to the first letter. After collecting them the last time, the words will be in order.
One problem with this method is that it depends on a large radix. A small radix makes the length of the items to be sorted larger, thus making the length of the items more significant than the number. Larger radixes, however, require more memory. If a large amount of memory is available, this sort can be extremely fast.
[Edit this page] [Page history] [What links here] [Discuss this topic] [Printer Friendly]
