Hacker News Reader

Comment by sawmurai | Hacker News Reader

Yep, should be

boolean[] result = new boolean[Math.max(array)];

That won't be efficient memorywise since the size of the result array is dependant on the largest value in the array of values.

Consider sorting an array of 2 large integers {65000,30000}. To sort this array, the result array will be initialized with 65000 elements. Very inefficient.

Yeah, well, now you get an exception. Not much better...

You should look into bucketsort. That allows you to sort in finite universes in Theta(n+k) without allocating huge arrays for large integers.

I will read more about bucketsort and update the article as necessary.

I have a simple Python implementation of Countingsort, Bucketsort and Radixsort, if it helps: https://github.com/MauriceGit/Advanced_Algorithms

Wouldn't using a sparse bit-array be equivalent to using Bucketsort in space-complexity, but more efficient in time-complexity, or am I missing something here.

Thanks a bunch for the link.

Using a sparse bit-array will reduce the memory space of the problem.

I can work up one. Choosing the right bucket will be O(1) as the index is integer. We can store the buckets for lookup in a hash-table or an array-of-arrays, which again will be O(1). Reaching to the actual index should again be O(1) - unless am messing something here.

Yes, but do you have an implementation of a sparse array with constant time lookups?

Reply on news.ycombinator.com