3
$\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$
1
  • $\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$ Dec 11, 2017 at 18:00

1 Answer 1

2
$\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$
3
  • $\begingroup$ Thanks for the lengthy explanation.. Suppose for a tight range of 1 to 100 of a large dataset, is counting sort or radix sort more appropriate? $\endgroup$ Dec 4, 2019 at 3:42
  • 1
    $\begingroup$ @RiyafaAbdulHameed without any more details, the counting sort seems more natural choice and will be faster with n counts instead of n*k operations. $\endgroup$
    – Evil
    Dec 4, 2019 at 3:59
  • $\begingroup$ Thank you for the reply. It is a dataset of ages of a large number of people. Counting sort makes more sense in this case. $\endgroup$ Dec 4, 2019 at 4:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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