Entiers «presque triés» en temps linéaire

Je souhaite trier un tableau de valeurs entières positives $L = v_1, \ldots, v_n$ en temps linéaire (dans le modèle RAM avec mesure de coût uniforme, c'est-à-dire que les entiers peuvent avoir jusqu'à la taille logarithmique mais les opérations arithmétiques sur eux sont supposées prendre le temps unitaire). Bien sûr, cela est impossible avec des algorithmes de tri basés sur la comparaison, donc je suis intéressé par le calcul d'un tri "approximatif", c'est-à-dire le calcul d'une permutation $v_{\sigma(1)}, \ldots, v_{\sigma(n)}$ de $L$qui est pas vraiment triés en général , mais une « bonne approximation » de la version triée de $L$ . Je suppose que nous trions les entiers par ordre décroissant car cela rend la suite un peu plus agréable à énoncer, mais bien sûr, on pourrait formuler le problème dans l'autre sens.

Un critère possible pour un tri approximatif est le suivant (*): laisser $N$ soit $\sum_i v_i$ , pour chaque $1 \leq i \leq n$ , nous exigeons que $v_{\sigma(i)} \leq N/i$ (c. -à- la « quasi-triai "La liste est délimitée par le haut par la fonction décroissante $i \mapsto N/i$ ). Il est facile de voir que le tri réel satisfait à ceci: $v_{\sigma(2)}$ doit pas être supérieur à $v_{\sigma(1)}$c'est donc au plus $(v_{\sigma(1)} + v_{\sigma(2)})/2$ qui est $\leq N/2$ , et en général $v_{\sigma(i)}$ doit pas être supérieur à $(\sum_{j \leq i} v_{\sigma(i)})/i$ qui est $\leq N/i$ .

Par exemple, l'exigence (*) peut être obtenue par l'algorithme ci-dessous (suggéré par @Louis). Ma question est la suivante: existe-t-il un travail sur cette tâche de "tri presque" des entiers en temps linéaire, en imposant une exigence comme (*) que le tri réel satisferait? L'algorithme ci-dessous, ou une variante de celui-ci, a-t-il un nom établi?

Edit: correction de l'algorithme et ajout de plus d'explications

Algorithme:

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

Cet algorithme fonctionne comme prévu pour les raisons suivantes:

1. Si un élément $v$ est dans le seau $j$ alors $v ≤ N/j$ .

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

2. Si un élément est dans le seau alors ou . $v$$j$$N/(j+1) < v$$j=n$

   $v$j = min ( N / v , n ) j = ⌊ N / est placé dans le seau , donc ou . Dans le premier cas qui signifie et donc .$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. Pour , il y a, au plus, éléments dans les godets de 1 à .$j<n$$j$$j$

   Soit $j<n$ et soit $k$ le nombre total d'éléments dans l'un des compartiments 1..j. Par 2. nous avons que chaque élément $v$ dans un seau $i$ (avec $i ≤ j$ ) est tel que $N/(j+1)≤N/(i+1)<v$ . Par conséquent, la somme $K$ de tous les éléments dans les godets de $1$ à $j$ est supérieure à $k×N/(J+1)$ . Mais cette somme$K$ est également inférieure à$N$ donc$k×N/(j+1) < K ≤ N$ et donc $k/(j+1) < 1$ ce qui nous donne$k<j+1$ ou$k≤j$ .

4. $T$ vérifie (*)dire la$j$ -ième élément de$T$ est telle que$T[j] ≤ N/j$

   Par 3. nous avons que $T[j]$ , le $j$ ème élément de $T$ , provient d'un seau $i$ avec $i ≥ j$ donc $T[j] ≤ N/i ≤ N/j$ .

5. Cet algorithme prend du temps linéaire.

   Le calcul de $N$ prend un temps linéaire. Les compartiments peuvent être implémentés avec une liste chaînée qui a une insertion et une itération $O(1)$ . La boucle imbriquée s'exécute autant de fois qu'il y a d'éléments (c'est-à-dire $n$ fois).

Cela ressemble beaucoup à l'algorithme ASort. Voir cet article de Giesen et. Al.:

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

Malheureusement, le temps de course n'est pas tout à fait linéaire. L'article ci-dessus prouve que tout algorithme randomisé basé sur une comparaison classant éléments dans n 2 / ν ( n ) a une borne inférieure de n ∗ l o g ( ν ( n ) ) (en supposant ν ( n ) < n ).$n$$n^2/\nu(n)$$n*log (\nu(n))$$\nu(n) < n$

EDIT , en réponse aux clarifications de la question:

Ce que vous faites est simplement une sorte de seau . Cependant, l'algorithme de tri par compartiment n'est pas linéaire dans ce cas. Le problème: vous devez additionner les nombres naturels puis effectuer la division sur chacun d'eux. Comme les nombres n'ont pas de taille illimitée, n'est plus une opération à temps constant. Il faudra plus de temps pour effectuer le plus de nombres que vous devez additionner.$N/V[i]$

Encore combien de temps? La division dépend du nombre de chiffres, c'est donc , fois n opérations de division. Cela semble probablement familier. :)$lg(n)$$n$

Il s'avère que ma question est tout à fait hors de propos après tout. En effet, je travaille sur la machine RAM avec une mesure de coût uniforme (c'est-à-dire que nous avons des registres dont les registres ne sont pas nécessairement de taille constante mais peuvent stocker des entiers de taille logarithmique au plus en entrée, et les opérations sur ces registres prennent un temps constant, y compris au moins addition). Et en fait, dans ce modèle, le tri des entiers (en effectuant essentiellement un tri radix) peut être effectué en temps linéaire. Ceci est expliqué dans l'article de 1996 de Grandjean, Sorting, temps linéaire et problème de satisfiabilité .

(Cela ne répond pas à ma question de savoir s'il existe des notions bien étudiées de "presque trier" un ensemble d'entiers, mais pour qu'elles soient intéressantes, il faudrait probablement que ces notions plus faibles soient plus faciles à appliquer, c'est-à-dire, travailler sur un plus faible modèle ou en quelque sorte exécuté en temps sublinéaire. Cependant, je ne suis actuellement pas au courant d'un sens dans lequel ce serait le cas.)