[macosxnerd101]

Radix sort is actually O(n log n). Binary sorting is O(n) though. The reason radix sort is O(n log n) is because the constant k really isn't constant. So radix is T(n) = kn. So we have n elements and we iterate k times, where k is the ceil of the logarithm of the largest element in the array.

[AdamSpeight2008]

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.

[macosxnerd101]

Quote

BIRST on strings is (Maximum string length + 1) passes, which is still linear.

I agree with the first part, but not the second. If you have bounded-size strings, yes, you can get a linear bound. However, for arbitrary sized strings, this comes out to log(n). If the string is base-10 integer, then the number of digits of the largest length string is on the order log(n), not constant.

Will you make the same number of iterations on [1, 2, 15, 30, 40] as [1000, 1520, 5833, 9101, 8585]? Obviously not. Thus, you can't conclude linear, as the "k" term in T(n) = kn is not a constant; rathern, k is a function of n and k(n) = O(log n).

[AdamSpeight2008]

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.

This post has been edited by AdamSpeight2008: 12 December 2013 - 06:28 PM

[macosxnerd101]

But that means that m can change, which means m isn't a constant and thus the algorithm isn't O(n) since m is on the order of log(n).

[AdamSpeight2008]

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

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.

This post has been edited by AdamSpeight2008: 12 December 2013 - 07:08 PM

[macosxnerd101]

Quote

It becomes a constant once you find m.

Adam- my point is that m is constant, only for a specific instance of the problem. It tells us nothing about a random list of integers. So the m for [1, 2, 15, 30, 40], is not the same as the m for [1000, 1520, 5833, 9101, 8585].

In fact, in the first example, m is roughly log_{10}(40); and in the second exapmle, m is roughly log_{10}(9101).

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.

[jon.kiparsky]

See previous discussion of "solving an instance" versus "solving the problem"...

[AdamSpeight2008]

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 )

This post has been edited by AdamSpeight2008: 12 December 2013 - 07:47 PM

[macosxnerd101]

Quote

But you can find m within an upper bound of O(n).

Doesn't matter. The m factor still varies based on the input, which means it isn't a constant; and thus, BIRST sort is *not* O(n).

[AdamSpeight2008]

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.

This post has been edited by AdamSpeight2008: 12 December 2013 - 07:56 PM

[macosxnerd101]

Per my Theory of Computation Text:

Quote

The symmetric functions are encountered in many applications. Among the important sym-
metric functions is binary sorting, the binary version of the standard sorting function. A
surprising fact holds for binary sorting, namely, that it can be realized on n
inputs by a circuit whose size is linear in n...Binary sorting, and all other symmetric functions, can be realized
efficiently through the use of a counting circuit that counts the number of 1’s among the
n inputs with a circuit of size linear in n. The counting circuit uses AND, OR,and NOT. When negations are disallowed, binary sorting requires on the order of n log n gates, as shown in Section 9.6.1

cs.brown.edu/~jes/book/pdfs/ModelsOfComputation.pdf

See page 74 (Section 2.11).

[AdamSpeight2008]

Straight out of the qoute

Quote

... binary sorting requires on the order of n log n gates ...

[macosxnerd101]

You missed this part:

Quote

When negations are disallowed, binary sorting requires on the order of n log n gates, as shown in Section 9.6.1

And right before that:

Quote

A surprising fact holds for binary sorting, namely, that it can be realized on n inputs by a circuit whose size is linear in n...Binary sorting, and all other symmetric functions, can be realized efficiently through the use of a counting circuit that counts the number of 1’s among the n inputs with a circuit of size linear in n.

[AdamSpeight2008]

Is this also an example of

Quote

"solving an instance" versus "solving the problem"...

as well.
As it is specific to Binary?

It essentially Counting Sort (I think).

Plus all that mathematical symbols makes looks like gobbly-gook to me.
Why do I tend to find that Mathematicians write for other Mathematician, and never for "Normal" people.

I ask to shows us an implementation in code. Not mathematics equations.

This post has been edited by AdamSpeight2008: 12 December 2013 - 08:44 PM