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.
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 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
o Sort by Name (String) o Sort by Room o Sort by ID
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.