4 ms·
Yep, should be boolean[] result = new boolean[Math.max(array)];
by sawmurai 10y ago
Yep, should be
boolean[] result = new boolean[Math.max(array)];
- ploggingdev 10y agoThat 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.
- EllipticCurve 10y agoYeah, 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.
- sangupta 10y agoI will read more about bucketsort and update the article as necessary.
- EllipticCurve 10y agoI have a simple Python implementation of Countingsort, Bucketsort and Radixsort, if it helps: https://github.com/MauriceGit/Advanced_Algorithms https://github.com/MauriceGit/Advanced_Algorithms
- sangupta 10y agoUsing a sparse bit-array will reduce the memory space of the problem.
- rhardih 10y agoYes, but do you have an implementation of a sparse array with constant time lookups?
- sangupta 10y agoI 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.