snippetMinor
sort n numbers in the range [0,1] without multiplying or dividing
Viewed 0 times
withouttherangenumbersmultiplyingdividingsort
Problem
Given an array with n real numbers, each in the range [0,1], I need to sort them. Moreover, the only operations that are allowed are comparisons or copying.
It means I cannot multiply or divide the numbers, which prohibits me from using bucket sort.
From what I learned, when you use only comparisons you cant sort any faster that O(nlogn). That means that I can just use any sort algorithm that achieves this bound, let's say heapsort, and be done with it.
However, in this way i don't use the info that the numbers are from the range [0,1]. For this reason, I'm not sure if I'm right.
It means I cannot multiply or divide the numbers, which prohibits me from using bucket sort.
From what I learned, when you use only comparisons you cant sort any faster that O(nlogn). That means that I can just use any sort algorithm that achieves this bound, let's say heapsort, and be done with it.
However, in this way i don't use the info that the numbers are from the range [0,1]. For this reason, I'm not sure if I'm right.
Solution
The $\Omega(n \log n)$ lower bound still applies; you still can't do better than $O(n \log n)$.
(Proof: Take any array of numbers. You can find the maximum and minimum in $O(n)$ time. Then, rescale the array. In particular, if the minimum and maximum are $\alpha$ and $\beta$, replace each element $x$ of the array with $(x-\alpha)/(\beta-\alpha)$. After the replacement, every element will be in the range $[0,1]$. If you had a way to sort such arrays faster than $O(n \log n)$, you'd immediately obtain a way to sort the original array faster than $O(n \log n)$.)
(Proof: Take any array of numbers. You can find the maximum and minimum in $O(n)$ time. Then, rescale the array. In particular, if the minimum and maximum are $\alpha$ and $\beta$, replace each element $x$ of the array with $(x-\alpha)/(\beta-\alpha)$. After the replacement, every element will be in the range $[0,1]$. If you had a way to sort such arrays faster than $O(n \log n)$, you'd immediately obtain a way to sort the original array faster than $O(n \log n)$.)
Context
StackExchange Computer Science Q#96394, answer score: 3
Revisions (0)
No revisions yet.