Reputation: 2161 Grandmaster
Group:
Mentors
Active Posts:
9,322 (4.61 per day)
Joined:
29-May 08
Profile Views:
117,199
Last Active:
A minute ago
Currently:
Viewing Blog Entry Developing a Generic Radix Sort

### Previous Fields

Country:
GB
OS Preference:
Windows
Favorite Browser:
Chrome
Favorite Processor:
Intel
Favorite Gaming Platform:
Playstation
Ford
Dream Kudos:
6275
Expert In:
vb.net, LINQ

### Latest Visitors

1. #### In Topic: Are there any P problems that were previously NP-Complete?

Posted 12 Dec 2013

What 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.
2. #### In Topic: Are there any P problems that were previously NP-Complete?

Posted 12 Dec 2013

macosxnerd101, on 13 December 2013 - 03:10 AM, said:

In 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

Quote

Analysis
Order: O(n) <= 2MN + 256M + 2M
Memory Footprint
```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 )
3. #### In Topic: Are there any P problems that were previously NP-Complete?

Posted 12 Dec 2013

It 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

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.
4. #### In Topic: Are there any P problems that were previously NP-Complete?

Posted 12 Dec 2013

I'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.
5. #### In Topic: Are there any P problems that were previously NP-Complete?

Posted 12 Dec 2013

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

### My Information

Member Title:
MrCupOfT
Age:
33 years old
Birthday:
December 20, 1979
Gender:
Location:
Behind You
VB.NET
Years Programming:
16

E-mail:
Private
Website URL:
http://

### Friends

Showing 50 random friends of 76  (View all)

• (2 Pages)
• 1
• 2
1. #### estherNamogo

03 Nov 2013 - 06:30
Hello
Nice to meet you write
me at (esther2namogo@hotmail.com) i will send you my picture OK.
2. #### bryanjay

12 Jul 2013 - 20:27
3. #### lucky3

31 Dec 2012 - 02:19
Congratulations for the "DIC Blog of the Year" award 1st place!
4. #### raghav.naganathan

15 Nov 2012 - 21:29
Hey...just to tell you this before your rep(1729) changes...:)
1729 is called Hardy-Ramanujan number :)
5. #### trevster344

17 Sep 2012 - 13:04
Excellent job with everything man, every tutorial, and over all everything you do here at D.I.C.
6. #### torind_2000

09 Aug 2012 - 08:58
Wanted to say thanks for all the info and resources you have gathered for us, it's been very useful.
7. #### modi123_1

30 Jul 2012 - 09:12
Quite the list of awards there..
8. #### Thailand

28 May 2012 - 07:30
Hi Adam, can you make a tutorial with how to make a multiplayer Texas H'oldem game please?
9. #### chyldlyk

08 Feb 2012 - 13:41
sir im a fan of yout post..very good tutorials..i really learned a lot..Sir i have a question where can i find your Walkthrough about update and delete using table adapter configuration wizard just like your username and password database..thank you for reading this..:D
10. #### DimitriV

05 Jan 2012 - 19:41
16 years programming? Nice effort!
11. #### awal

25 Mar 2011 - 04:32
nice
12. #### BenignDesign

11 Apr 2010 - 10:05
Is that you? Looks like a young Bono. Weird.
13. #### Salmancom

28 Mar 2010 - 03:26
hi..
14. #### mbrother64

26 Mar 2010 - 00:49
hello
15. #### kunal.jaiswal

01 Mar 2010 - 04:04
hi r u there
• (2 Pages)
• 1
• 2