Enteros de "casi clasificación" en tiempo lineal

Estoy interesado en ordenar una matriz de valores enteros positivos $L = v_1, \ldots, v_n$ en tiempo lineal (en el modelo RAM con una medida de costo uniforme, es decir, los enteros pueden tener un tamaño logarítmico pero se supone que las operaciones aritméticas en ellos tomar unidad de tiempo). Por supuesto, esto es imposible con algoritmos de clasificación basados ​​en comparación, por lo que estoy interesado en calcular un tipo "aproximado", es decir, calcular alguna permutación $v_{\sigma(1)}, \ldots, v_{\sigma(n)}$ de $L$que no es realmente ordenados en general, sino una "buena aproximación" de la versión ordenada de $L$ . Asumiré que estamos ordenando los enteros en orden decreciente porque hace que la secuela sea un poco más agradable de decir, pero, por supuesto, uno podría expresar el problema al revés.

Un posible criterio para una clasificación aproximada es el siguiente (*): dejando que $N$ sea $\sum_i v_i$ , por cada $1 \leq i \leq n$ , requerimos que $v_{\sigma(i)} \leq N/i$ (es decir, el "cuasi-ordenado "la lista está limitada desde arriba por la función decreciente $i \mapsto N/i$ ). Es fácil ver que el tipo real satisface esto: $v_{\sigma(2)}$ debe ser mayor que $v_{\sigma(1)}$entonces es como máximo $(v_{\sigma(1)} + v_{\sigma(2)})/2$ que es $\leq N/2$ , y en general $v_{\sigma(i)}$ debe ser mayor que $(\sum_{j \leq i} v_{\sigma(i)})/i$ que es $\leq N/i$ .

Por ejemplo, el requisito (*) puede lograrse mediante el algoritmo a continuación (sugerido por @Louis). Mi pregunta es: ¿Existe trabajo en esta tarea de "casi ordenar" enteros en tiempo lineal, imponiendo algún requisito como (*) que el tipo real satisfaría? ¿El algoritmo a continuación, o alguna variante del mismo, tiene un nombre establecido?

Editar: corrigió el algoritmo y agregó más explicaciones

Algoritmo:

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

Este algoritmo funciona según lo previsto por los siguientes motivos:

1. Si un elemento $v$ está en el cubo $j$ entonces $v ≤ N/j$ .

   $v$ se coloca en el cubo$j=\min(N/v,n)$ , por lo tanto$j ≤ \lfloor N/v\rfloor ≤ N/v$

2. Si un elemento $v$ está en el depósito $j$ entonces $N/(j+1) < v$ o $j=n$ .

   $v$ se coloca en el cubo$j=\min(N/v,n)$ , por lo tanto$j = \lfloor N/v \rfloor$ o$j=n$ . En el primer caso,$j=\lfloor N/v\rfloor$ que significa$j ≤ N/v < j+1$ y, por lo tanto,$N/(j+1) < v$ .

3. Para $j<n$ , hay, a lo sumo, elementos $j$ en los cubos de 1 a $j$ .

   Sea $j<n$ y sea $k$ el número total de elementos en uno de los cubos 1..j. Por 2. tenemos que cada elemento $v$ en un cubo $i$ (con $i ≤ j$ ) es tal que $N/(j+1)≤N/(i+1)<v$ . Por lo tanto, la suma $K$ de todos los elementos en los cubos de $1$ a $j$ es mayor que $k×N/(J+1)$ . Pero esta suma$K$ también es menor que$N$ tanto,$k×N/(j+1) < K ≤ N$ y, por lo tanto, $k/(j+1) < 1$ que nos da$k<j+1$ o$k≤j$ .

4. $T$ satisface (*) es decir, elelemento$j$ -ésimo de$T$ es tal que$T[j] ≤ N/j$

   Por 3. tenemos que $T[j]$ , el elemento $j$ -ésimo de $T$ , proviene de un cubo $i$ con $i ≥ j$ por lo tanto $T[j] ≤ N/i ≤ N/j$ .

5. Este algoritmo lleva tiempo lineal.

   El cálculo de $N$ toma tiempo lineal. Los cubos se pueden implementar con una lista vinculada que tiene inserción e iteración $O(1)$ . El bucle anidado se ejecuta tantas veces como haya elementos (es decir, $n$ veces).

Esto se parece mucho al algoritmo ASort. Ver este artículo de Giesen et. Alabama.:

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

Desafortunadamente, el tiempo de ejecución no es del todo lineal. El artículo anterior demuestra que cualquier algoritmo aleatorio basado en comparación que clasifica elementos dentro de n 2 / ν ( n ) tiene un límite inferior de n ∗ l o g ( ν ( n ) ) (suponiendo que ν ( n ) < n ).$n$$n^2/\nu(n)$$n*log (\nu(n))$$\nu(n) < n$

EDITAR , en respuesta a las aclaraciones en la pregunta:

Lo que estás haciendo es simplemente una especie de cubo . Sin embargo, el algoritmo para la clasificación de cubetas no es lineal en este caso. El problema: tienes que sumar los números naturales y luego realizar la división en cada uno de ellos. Como los números no tienen límites de tamaño, ya no es una operación de tiempo constante. Tomará más tiempo realizar los números que necesita sumar.$N/V[i]$

¿Cuanto tiempo más? La división depende del número de dígitos, por lo que es , multiplicado por n operaciones de división. Eso probablemente suena familiar. :)$lg(n)$$n$

Como resultado, mi pregunta es bastante irrelevante después de todo. De hecho, estoy trabajando en la máquina RAM con una medida de costo uniforme (es decir, tenemos registros cuyos registros no son necesariamente de tamaño constante pero pueden almacenar enteros de tamaño logarítmico en la entrada como máximo, y las operaciones en estos registros toman tiempo constante, incluyendo al menos además). Y, de hecho, en este modelo, la clasificación de enteros (al realizar esencialmente una clasificación de radix) se puede hacer en tiempo lineal. Esto se explica en el artículo de 1996 de Grandjean, Clasificación, tiempo lineal y el problema de la satisfacción .

(Esto no responde a mi pregunta de si hay nociones bien estudiadas de "casi ordenar" un conjunto de enteros, pero para que sean interesantes, uno probablemente necesitaría estas nociones más débiles para que sean más fáciles de aplicar, es decir, trabajar en un más débil modelo o de alguna manera ejecutado en tiempo sublineal. Sin embargo, actualmente no estoy al tanto de un sentido en el que este sería el caso).