Geodesic
Complexity of self-correcting algorithms for two sorting problems
Diskretnaya Matematika, Tome 1 (1989) no. 3, pp. 111-120 
V. V. Morozenko. Complexity of self-correcting algorithms for two sorting problems. Diskretnaya Matematika, Tome 1 (1989) no. 3, pp. 111-120. http://geodesic.mathdoc.fr/item/DM_1989_1_3_a11/
@article{DM_1989_1_3_a11,
     author = {V. V. Morozenko},
     title = {Complexity of self-correcting algorithms for two sorting problems},
     journal = {Diskretnaya Matematika},
     pages = {111--120},
     year = {1989},
     volume = {1},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_1989_1_3_a11/}
}
TY  - JOUR
AU  - V. V. Morozenko
TI  - Complexity of self-correcting algorithms for two sorting problems
JO  - Diskretnaya Matematika
PY  - 1989
SP  - 111
EP  - 120
VL  - 1
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DM_1989_1_3_a11/
LA  - ru
ID  - DM_1989_1_3_a11
ER  - 
%0 Journal Article
%A V. V. Morozenko
%T Complexity of self-correcting algorithms for two sorting problems
%J Diskretnaya Matematika
%D 1989
%P 111-120
%V 1
%N 3
%U http://geodesic.mathdoc.fr/item/DM_1989_1_3_a11/
%G ru
%F DM_1989_1_3_a11

Voir la notice de l'article provenant de la source Math-Net.Ru

For a standard sorting problem for an $n$-element set we obtain an algorithm, optimal with respect to order, that corrects up to $k(n)$ incorrect comparisons of elements of a sortable set. We show that this algorithm is asymptotically optimal when $k=o(\log n)$. We also obtain a self-correcting algorithm, optimal with respect to order, for a sorting problem of a set that is isomorphic to a Boolean algebra.