Reputation: 2161 Grandmaster
- Active Posts:
- 9,322 (4.61 per day)
- 29-May 08
- Profile Views:
- Last Active:
- A minute ago
- Viewing Blog Entry Developing a Generic Radix Sort
- OS Preference:
- Favorite Browser:
- Favorite Processor:
- Favorite Gaming Platform:
- Your Car:
- Dream Kudos:
- Expert In:
- vb.net, LINQ
Posts I've Made
Posted 12 Dec 2013What it Binary Sorting?
DIC mantra is "Show us your Code"
Ot are you confused with Binary Search?
BIRST could be performed a bit level but the increases the size of m.
Posted 12 Dec 2013In order for BIRST sort to be linear, the same constant has to be used for any input array. This is just not the case, as you have clearly demonstrated.
No it doesn't.
If you can find m within an upper bound of O(n). Which you can.
BIRST sort is O(mn + n) => O(n) the + 1 is the finding of the maximum length of string. Bytewise radix is O(4n) => O(n) m = 4 How many bytes wide is this number. On a 64bit m = 8. HalfWord-wise radix is O(2n) => O(n) m = 2 On a 64bit m = 4. Counting Sort is O(2n) => O(n) m = 2
So how come BIRST (radix) sort is any different different to the others? It isn't
The tutorial include an fuller analysis of the time complexity
Order: O(n) <= 2MN + 256M + 2M
Byte Index Array = 256 * 2 * 4 bytes =>2048b / 2Kb Radix Sort = n * 2 * 4 bytes LIst Positon = n * 4 bytes
Show me a a Sublinear sorting algortithm? (Excluding algorithms that require quantum computation )
Posted 12 Dec 2013It becomes a constant once you find m. For 32bits this is typically 4 (Bytewise Radix) or 32 (Bitwise Radix)
In Bubble Sort, n changes for each of the inner iterations, where as in radix it stays constant at n.
n = strings.Length Bubble Sort you do C comparisions n² - n c = ------ 2 Radix m = strings.Max( s=> s.Length ) r = m * n
If n = 1000000 and m = 256 then
c = 499999500000
r = 256000000
which is an order of magnitude smaller.
Posted 12 Dec 2013I'm saying it linear once you found the maximum length of string contained in the string array.
n = strings.Count ' O(1) m = strings.Max( s=> s.Length ) ' O(n) s.Length is O(1) in .net BIRST( strings ) ' O(m * n)
You'll do m passes over the array.
For pass = 0 To (m-1) ' rest of BIRST sort algorithm. Next
The "Radix Indexes" is essential a linked list (Pointing to first in the chain and the last in the chain)
After going through each string. You join the linked-lists together Each "Radix Index".LastNode is set to point at the FirstNode of the next "Radix Index".FirstNode. Each node points to it related Data (string) and has a pointer to the next Node.
In the next iteration of the radix loop you use as input this chain, etc
After all of the iterations you walk through the linked list and copy the corresponding data accoss into a new array. And return it.
The results for your examples would be.
[1, 2, 15, 30, 40] n = 5 m = 2 O = (5 * 2) = 10 [1000, 1520, 5833, 9101, 8585] n = 5 m = 4 O = (5 * 4) = 20
Blog Entry: Developing a Generic Radix Sort
Which use BIRST Sort as it Radix Sort implementation.
Posted 12 Dec 2013Look at the BIRST algorithm again cos it definitely linear. Sorting an array of Int32 takes 4 passes (assume 1 byte indexing), regardless of the size of the array.
BIRST on strings is (Maximum string length + 1) passes, which is still linear.
- Member Title:
- 33 years old
- December 20, 1979
- Behind You
- Forum Leader:
- Years Programming:
- Website URL:
Showing 50 random friends of 76 (View all)