8 ms·
In https://github.com/sangupta/ps/blob/master/solutions/2016/fastest-sorting-integers.md https://github.com/sangupta/ps/blob/master/solutions/2016/fa... the sol
by ploggingdev 10y ago
In https://github.com/sangupta/ps/blob/master/solutions/2016/fastest-sorting-integers.md https://github.com/sangupta/ps/blob/master/solutions/2016/fa... the solution for fastest integer sorting is wrong.
/ build the boolean result array
boolean[] result = new boolean[array.length];
for(int index = 0; index < array.length; index++) {
int num = array[index];
result[num] = true;
}
The result array is the same size as the original array.
But when you do:
int num = array[index];
result[num] = true;
The index being referenced in the result array is dependent on the value of num. So if num is greater than or equal to the length of the array, it throws an ArrayOutOfBoundsException. And what happens when you try sorting an array with elements having the same value?
Eg- try sorting {10,5,9}
Unrelated: HN needs to allow highlighting code inline.
- sawmurai 10y agoYep, 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.
- sangupta 10y agoMy bad - that was a typo when writing. Updating it.
- jedimastert 10y agoIn the prompt, he says we are looking at a "bounded" integer set, so presumably we know the largest possible number before we start