2
$\begingroup$

Okay can't figure this out. I want to make sure I understand it.
There are n random keys each being float numbers with p decimal places. So, for example, 123.456,

343.645,

234.543,

863.238,

956.043,

etc.

For which values of p should you use counting sort, radix sort, and merge sort to make it the fastest. I know counting sort runs O(n+k), radix runs O(d(n+k)), and merge is O(n) in its best case. Also, I *think when sorting with decimals you first multiply each by 1000 (in this case) to make them whole numbers, correct? Or is that wrong? Any and all help would be appreciated.

$\endgroup$
  • $\begingroup$ The question doesn't seem answerable. $O(\cdot)$ notation hides too much implementation detail that any answer would have to depend on. For example, suppose you have an $O(n)$ algorithm and an $O(n^2)$. If the former takes $10^9n$ steps and the latter takes exactly $n^2$ steps, then the quadratic algorithm is faster for all $n\leq 10^9$, but you can't tell that if all you know is $O(n)$ and $O(n^2)$. $\endgroup$ – David Richerby Dec 11 '17 at 18:00
1
$\begingroup$

The idea seems wrong at its core. The missing parts are: what is the distribution and range of the data. How many items do you have? (You may not know this in advance, but it renders some algorithms useless).

The counting sort works well when the range is compact, it gives good memory requirements and the mere array traversal is not computationally expensive. In the case of floating-point numbers, when you multiply decimal part to make full integers the range may be huge, in that case $n$ may be small but $k$ is huge. Instead of multiplying them out the better idea is to round them and store only decimal part. This idea would not blow up the range and after counting you are left with small bins to sort. To give more or less answer to $p$ parameter, it really depends on scarcity of data and number, but say, if you really want to multiply them by $10^p$ in many cases for $p \ge 3$ it seems like bad idea.

The radix sort depends on $d$ which is the number of digits, here it doesn't matter where is the decimal point, but with bigger $p$ the $d$ is bigger, which kills the performance (unless bigger radix is used for decimal part only).

Merge sort, the natural variant, is $\mathcal O(n)$ but this property is not that important to choose, it effectively says that the algorithm terminates sorting early when it gets sorted data. The best case for sorting (when applicable by algorithm properties) must be $\Omega(n)$ to at least read the input and check whether consecutive numbers obey order. Merge sort runtime does not depend on $p$, as far it is some built-in type, unless the float is stored as the string, but this on its own may be problematic and performance killer. The access to decimal digits in case of some floating-point number requires conversion, which takes time or additional memory.

To choose sorting algorithm the first step is to match inherent properties with data, use (or add if you have to) properties like stability of sorting, understand what asymptotic notation mean, look at average case and test with your real data.

Why $n$ is important here? Because if it is small (10-20) Bubble sort is faster on average than other algorithms (short of counting sort with extremely tight range), because it has small hidden constant and for non-artificial data it does rarely encounter bad case. The situation gets more complicated when actual data is bigger, but in the case of smallish data, say 1000 – 20000 items, the hidden constant still matters.

For data in your format (3 digit decimals with $p$ decimal places) if you know distribution, it may be beneficial to use distribution sort or counting sort, rounding numbers beforehand. Back to your question, the decision to select one of given algorithms doesn't solely depend on $p$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.