We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
You can't achieve O(n) through bucket sort if you don't know if the input is random. In this problem it is not directly stated. If it was, bucket would seem to be a nice option indeed.
Radix works better for strings, sure longer than 10 digits. Constant factor for such sorting would be unnecessary big, make it slower than qsort.
And you have to be careful with count sort - its speed depends on range of numbers so,
instead of O(n log n) (for qsort n = 10^5) you get O(n) (where n = ai = 10^9).
And, cause
10^5 * log(10^5) < 10^9
log(10^5) < 10^4
then count works longer for big input.
Also, for input like
{0, 10^9}
count sort still needs O(10^9) time.
Minimum Absolute Difference in an Array
You are viewing a single comment's thread. Return to all comments →
But that'd be like worse than O(n log n). Guess we could sort by count or radix or bucket to achieve O(n) in sorting
You can't achieve O(n) through bucket sort if you don't know if the input is random. In this problem it is not directly stated. If it was, bucket would seem to be a nice option indeed.
Radix works better for strings, sure longer than 10 digits. Constant factor for such sorting would be unnecessary big, make it slower than qsort.
And you have to be careful with count sort - its speed depends on range of numbers so, instead of O(n log n) (for qsort n = 10^5) you get O(n) (where n = ai = 10^9).
And, cause
then count works longer for big input.
Also, for input like {0, 10^9} count sort still needs O(10^9) time.