18
$\begingroup$

I am interested in sorting an array of positive integer values $L = v_1, \ldots, v_n$ in linear time (in the RAM model with uniform cost measure, i.e., integers can have up to logarithmic size but arithmetic operations on them are assumed to take unit time). Of course, this is impossible with comparison-based sorting algorithms, so I am interested in computing an "approximate" sort, i.e., computing some permutation $v_{\sigma(1)}, \ldots, v_{\sigma(n)}$ of $L$ which is not really sorted in general but a "good approximation" of the sorted version of $L$. I will assume that we are sorting the integers in decreasing order because it makes the sequel a bit more pleasant to state, but of course one could phrase the problem the other way round.

One possible criterion for an approximate sort is the following (*): letting $N$ be $\sum_i v_i$, for every $1 \leq i \leq n$, we require that $v_{\sigma(i)} \leq N/i$ (i.e., the "quasi-sorted" list is bounded from above by the decreasing function $i \mapsto N/i$). It is easy to see that the actual sort satisfies this: $v_{\sigma(2)}$ must be no greater than $v_{\sigma(1)}$ so it is at most $(v_{\sigma(1)} + v_{\sigma(2)})/2$ which is $\leq N/2$, and in general $v_{\sigma(i)}$ must be no greater than $(\sum_{j \leq i} v_{\sigma(i)})/i$ which is $\leq N/i$.

For instance, requirement (*) can be achieved by the algorithm below (suggested by @Louis). My question is: Is there existing work on this task of "almost sorting" integers in linear time, by imposing some requirement like (*) that the real sort would satisfy? Does the algorithm below, or some variant of it, have an established name?

Edit: fixed the algorithm and added more explanations


Algorithm:

INPUT: V an array of size n containing positive integers
OUTPUT: T

N = Σ_{i<n} V[i]
Create n buckets indexed by 1..n
For i in 1..n
| Add V[i] into the bucket min(floor(N/V[i]),n)
+

For bucket 1 to bucket n
| For each element in the bucket
| | Append element to T
| +
+

This algorithm works as intended for the following reasons:

  1. If an element $v$ is in the bucket $j$ then $v ≤ N/j$.

    $v$ is put into the bucket $j=\min(N/v,n)$, thus $j ≤ \lfloor N/v\rfloor ≤ N/v$

  2. If an element $v$ is in the bucket $j$ then either $N/(j+1) < v$ or $j=n$.

    $v$ is put into the bucket $j=\min(N/v,n)$, thus $j = \lfloor N/v \rfloor$ or $j=n$. In the first case $j=\lfloor N/v\rfloor$ which means $j ≤ N/v < j+1$ and thus $N/(j+1) < v$.

  3. For $j<n$, there are, at most, $j$ elements in the buckets from 1 to $j$.

    Let $j<n$ and let $k$ be the total number of elements in one of the buckets 1..j. By 2. we have that every element $v$ in a bucket $i$ (with $i ≤ j$) is such that $N/(j+1)≤N/(i+1)<v$. Therefore the sum $K$ of all elements in the buckets from $1$ to $j$ is greater than $k×N/(J+1)$. But this sum $K$ is also less than $N$ thus $k×N/(j+1) < K ≤ N$ and thus $k/(j+1) < 1$ which gives us $k<j+1$ or $k≤j$.

  4. $T$ satisfies (*) i.e. the $j$-th element of $T$ is such that $T[j] ≤ N/j$

    By 3. we have that $T[j]$, the $j$-th element of $T$, comes from a bucket $i$ with $i ≥ j$ therefore $T[j] ≤ N/i ≤ N/j$.

  5. This algorithm takes linear time.

    The computation of $N$ takes linear time. Buckets can be implemented with a linked-list which has $O(1)$ insertion and iteration. The nested loop runs as many times as there are elements (i.e. $n$ times).

$\endgroup$
8
  • 1
    $\begingroup$ Not to dismiss the question (+1, it's a good one) but wouldn't radix sort do more than what you need? $\endgroup$
    – user541686
    Apr 24, 2017 at 21:28
  • $\begingroup$ @Mehrdad: Thanks for your comment! Radix sort would sort the integers, but it would take time $O(n \log (\max_i v_i))$. $\endgroup$
    – a3nm
    Apr 25, 2017 at 15:43
  • $\begingroup$ Could you comment on what exactly is undesirable about that time complexity? Do you have one very large integer and everything else is small, for example? $\endgroup$
    – user541686
    Apr 25, 2017 at 17:34
  • 1
    $\begingroup$ @a3nm radix sort is not O(n log n) it is O(n) hence linear if the size of integers is fixed, for example 32 bits numbers or 64 bits numbers. Does the numbers you sort have variable size? $\endgroup$ Apr 27, 2017 at 7:53
  • 1
    $\begingroup$ @XavierCombelle: Yes, I'm working in the RAM model and I cannot suppose that the input integers are bounded by a constant. $\endgroup$
    – a3nm
    Apr 27, 2017 at 8:39

2 Answers 2

8
$\begingroup$

This sounds a lot like the ASort algorithm. See this article by Giesen et. al.:

https://www.inf.ethz.ch/personal/smilos/asort3.pdf

Unfortunately, the running time is not quite linear. The article above proves that any comparison-based randomized algorithm ranking $n$ items within $n^2/\nu(n)$ has a lower bound of $n*log (\nu(n))$ (assuming $\nu(n) < n$).


EDIT, in response to the clarifications in the question:

What you're doing is simply a bucket sort. However, the algorithm for bucket sort isn't linear in this case. The problem: you have to sum the natural numbers and then perform division on each one of them. Since the numbers are unbounded in size, $N/V[i]$ is no longer a constant-time operation. It will take longer to perform the more numbers you need to sum.

How much longer? Division depends on the number of digits, so it's $lg(n)$, times $n$ division operations. That probably sounds familiar. :)

$\endgroup$
5
  • 1
    $\begingroup$ Thanks for pointing us to this article! Indeed it is a bit related to the question. However, my algorithm (neither the original version nor the slightly different revised version) is not so similar to ASort;. First, I believe my algorithm runs in $O(n)$, not in superlinear time like ASort. Second, criterion (*) is pretty different from approximating Spearman's footrule distance; e.g., criterion (*) is more or less tight depending on the values of the integers, unlike the footrule distance. Third, althout both our algorithm and ASort are bucketing elements, the criteria are pretty different. $\endgroup$
    – a3nm
    Apr 25, 2017 at 15:44
  • $\begingroup$ @a3nm The clarification of what you posted above suggests you're using a bucket sort, which is linear (and not comparison-based, which means testing two items against each other). The problem is that it doesn't work for all mathematical integers. It only works if the integer size is bounded. $\endgroup$ Apr 27, 2017 at 16:21
  • $\begingroup$ When you say "It only works if the integer size is bounded", I think this is only true if I were actually sorting the integers. But in general the algorithm I posted does not actually sort them, it only enforces the weaker criterion (*). So I do think it runs in linear time even when the integer size is not bounded. $\endgroup$
    – a3nm
    Apr 28, 2017 at 6:22
  • 2
    $\begingroup$ @a3nm It isn't linear. See my expanded response above. $\endgroup$ Apr 29, 2017 at 2:04
  • $\begingroup$ Thanks for the answer, and sorry about the delay. I think there is some confusion about the model. I am working in the RAM model with uniform time measure (as in van Emde Boas, Machine Models and Simulations, in Handbook of Computation): so the numbers that I manipulate can have logarithmic size, but arithmetic operations on these numbers have unit cost. I have edited my question accordingly. I think that, in this model, the algorithm that I propose really runs in linear time (but of course in this model the $n \log n$ lower bound for actual comparison-based sorting still applies). $\endgroup$
    – a3nm
    May 9, 2017 at 9:42
2
$\begingroup$

As it turns out, my question is quite irrelevant after all. Indeed, I am working on the RAM machine with uniform cost measure (i.e., we have registers whose registers are not necessarily of constant size but can store integers of logarithmic size in the input at most, and operations on these registers take constant time, including at least addition). And in fact, in this model, sorting integers (by essentially performing a radix sort) can be done in linear time. This is explained in the 1996 paper by Grandjean, Sorting, linear time and the satisfiability problem.

(This does not answer my question of whether there are well-studied notions of "almost sorting" a set of integers, but for them to be interesting one would probably need these weaker notions to be easier to enforce, i.e., work on a weaker model or somehow run in sublinear time. However, I'm currently not aware of a sense in which this would be the case.)

$\endgroup$

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.