«Почти сортировка» целых чисел за линейное время

Меня интересует сортировка массива положительных целочисленных значений за линейное время (в модели оперативной памяти с одинаковой мерой стоимости, т. Е. Целые числа могут иметь размер до логарифмического, но предполагается, что арифметические операции над ними будут выполняться единица времени). Конечно, это невозможно с помощью алгоритмов сортировки, основанных на сравнении, поэтому мне интересно вычислить «приблизительную» сортировку, то есть вычислить некоторую перестановку из , который на самом деле не сортируется в целом , а «хорошее приближение» из отсортированной версии . Я буду предполагать, что мы сортируем целые числа в порядке убывания, потому что это делает продолжение более приятным, но, конечно, можно сформулировать проблему наоборот.$L = v_1, \ldots, v_n$$v_{\sigma(1)}, \ldots, v_{\sigma(n)}$$L$$L$

Одним из возможных критериев приближенной сортировки является следующее (*): если будет , то для каждого мы требуем, чтобы (т.е. «квази-отсортированный» список сверху ограничен убывающей функцией ). Легко видеть, что фактическая сортировка удовлетворяет этому: должно быть больше, чем поэтому оно не больше есть , и в общем случае должно превышать который является$N$$\sum_i v_i$$1 \leq i \leq n$$v_{\sigma(i)} \leq N/i$$i \mapsto N/i$$v_{\sigma(2)}$$v_{\sigma(1)}$$(v_{\sigma(1)} + v_{\sigma(2)})/2$$\leq N/2$$v_{\sigma(i)}$$(\sum_{j \leq i} v_{\sigma(i)})/i$$\leq N/i$,

Например, требование (*) может быть достигнуто с помощью алгоритма ниже (предложено @Louis). Мой вопрос: существует ли работа по этой задаче «почти сортировки» целых чисел в линейном времени, навязывая какое-то требование типа (*), которое бы удовлетворяла реальная сортировка? Имеет ли приведенный ниже алгоритм или какой-либо его вариант установленное имя?

Редактировать: исправлен алгоритм и добавлено больше объяснений

Алгоритм:

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
| +
+

Этот алгоритм работает как задумано по следующим причинам:

1. Если элемент $v$ находится в сегменте $j$ то $v ≤ N/j$ .

   $v$$j=\min(N/v,n)$$j ≤ \lfloor N/v\rfloor ≤ N/v$

2. Если элемент находится в сегменте то либо либо . $v$$j$$N/(j+1) < v$$j=n$

   $v$ помещается в ведро$j=\min(N/v,n)$ , таким образом$j = \lfloor N/v \rfloor$ или$j=n$ . В первом случае$j=\lfloor N/v\rfloor$ что означает$j ≤ N/v < j+1$ и, следовательно,$N/(j+1) < v$ .

3. Для $j<n$ в сегментах от 1 до j имеется не более $j$ элементов .$j$

   Пусть $j<n$ и $k$ - общее количество элементов в одном из сегментов 1..j. В силу 2. имеем, что каждый элемент $v$ в сегменте $i$ (с $i ≤ j$ ) таков, что $N/(j+1)≤N/(i+1)<v$ . Следовательно, сумма $K$ всех элементов в сегментах от $1$ до $j$ больше, чем $k×N/(J+1)$ . Но эта сумма$K$ также меньше$N$ поэтому$k×N/(j+1) < K ≤ N$ и, следовательно, $k/(j+1) < 1$ что дает нам$k<j+1$ или$k≤j$ .

4. $T$ удовлетворяет (*), т.Е.$j$ элемент$T$ таков, что$T[j] ≤ N/j$

   Согласно 3. мы имеем, что $T[j]$ , $j$ элемент $T$ , происходит из сегмента $i$ с $i ≥ j$ поэтому $T[j] ≤ N/i ≤ N/j$ .

5. Этот алгоритм занимает линейное время.

   Вычисление $N$ занимает линейное время. Контейнеры могут быть реализованы с помощью связанного списка, который содержит вставку и итерацию $O(1)$ . Вложенный цикл выполняется столько раз, сколько существует элементов (т.е. $n$ раз).

Это очень похоже на алгоритм ASort. Смотрите эту статью Giesen et. и др .:

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

$n$$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. :)

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.)