View this PageEdit this PageAttachments to this PageHistory of this PageHomeRecent ChangesSearch the SwikiHelp Guide
Hotspots: Admin Pages | Turn-in Site |
Current Links: Cases Final Project Summer 2007

Radix Sort - Hyung-Min Lee

Radix Sort


O(n*k)
Use Radix sort to achieve better than O(nlogn) search. (for those who don't know what this means, it means really fast.

What is Radix Sort?

   What is Radix?
    o Root in Latin
    o In arithmetic, base of an exponential expression.
    o Base of Positional Numeral System
        Number of unique digits, including zero, that a positional numeral system uses to represent numbers.
        For decimal system, the radix is 10
        Binary: 2      Octal: 8      Hexadecimal: 16
   What is Radix Sort?
    o Sorting data by digit.

Why Radix Sort?

   Sort integers or any other data format that can be represented as integers(i.e. String) fast.
                   O(n*k)
                    n: number of keys
                    k: length of key

How Radix Sort?

   How To: LSD(Least Significant Digit) Radix Sort
     1.Hash Table with size equal to the radix of key
     2.Hash data with right most digit of key
     3.Rehash with one level higher digit than before
     4.Repeat k times
     5.Retrieve data from hash table in order

   Example:
     Sort the following data using Radix Sort.
       170  45  75  90  2  24  802  66  25

   Create hash table with size of the radix.
   - 170  45  75  90  2  24  802  66  25
   0
   1
   2
   3
   4
   5
   6
   7
   8
   9

   Hashing using first digit
   - 45  75  90  2  24  802  66  25
   0 170
   1
   2
   3
   4
   5
   6
   7
   8
   9

   - 24  802  66  25
   0 170 90
   1
   2 2
   3
   4 
   5 45 75
   6
   7
   8
   9

   - 
   0 170 90
   1
   2 2 802
   3
   4 24
   5 45 75 25
   6 66
   7
   8
   9

   Retrieve data in order.
   - 170  90  2  802  24  45  74  25  66
   0
   1
   2
   3
   4
   5
   6
   7
   8
   9

   Rehash using second digit
   - 
   0 02 802
   1
   2 24 25
   3
   4 45
   5
   6 66
   7 170 74
   8
   9 90

   Retrieve data in order.
   - 2  802  24  25  45  66  170  74  90
   0
   1
   2
   3
   4
   5
   6
   7
   8
   9

   Rehash using third digit.
   - 
   0 002 024 025 045 066 074 090
   1 170 
   2
   3
   4
   5
   6
   7
   8 802
   9

   Retrieve data in order.
   - 2  24  25  45  66  74  90  170  802
   0
   1
   2
   3
   4
   5
   6
   7
   8
   9

   Data is now sorted
     2  24  25  45  66  74  90  170  802

When Radix Sort?

    o Sort by Name (String)
    o Sort by Room
    o Sort by ID

Why Radix Sort in Smalltalk?

    In small talk it is possible to send in code blocks as parameters to a message.
    So if implemented correctly, a Radix Sort class can take in a code block for hash code.
    This means the user is not limited to use hash code provided by the data type class.
    User can send in custom code block to generate integer keys to sort by.

Link to this Page