Hotspots: Admin Pages | Turn-in Site |
Current Links: Cases Final Project Summer 2007

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?
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
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.