Trier un tableau de

J'essaie de comprendre comment trier un tableau de $n$ éléments quand seulement $\log n$ ne sont pas en place.

J'ai entendu dire que trier un tableau avec au plus $I$ les inversions ont de la complexité $O(n\log(I/n))$. Parce qu'il y a$\log n$ éléments qui ne sont pas triés, dans mon cas il y a au plus $n\log n$ inversion.

La réponse à la question est $O(n\log\log n)$ ce qui est cohérent avec la formule, mais je ne comprends pas "l'idée derrière elle, ni quel algorithme de tri y parvient.

En admettant que "$k$ éléments hors de propos "signifie qu'il existe $k$ les éléments dont la suppression laisse le reste du tableau trié, il y a un $O(n+k\log k)$-algorithme de temps pour trier le tableau entier.

En un mot, calculer une sous-séquence croissante de longueur au moins $n-2k$, triez les autres et fusionnez. Le premier peut être accompli à temps$O(n)$par un simple algorithme de pile qui pousse les éléments un par un et fait apparaître les deux premiers lorsqu'ils sont en panne. La stratégie de suppression optimale doit supprimer au moins un de ces éléments, de sorte que le dommage total est limité par$2k$ suppressions.

Disons qu'il y a $k$ éléments non en place.

Divisez le tableau en sous-réseaux non décroissants. Cela peut être fait en$\Theta(n)$ temps et se traduira par au plus $2k$sous-réseaux. Maintenant, nous les fusionnons simplement par paires$\Theta(n \log k)$ temps, ce qui donne un tableau trié.