Tri en ligne sans modifications

Question

Il y a un tableau avec $ n $ places. Il y a un flux de numéros uniques $ N $ qui arrivent à un ordre aléatoire (permutation sélectionnée uniformément au hasard).

Chaque fois qu'un nombre arrive, nous devons le mettre quelque part dans le tableau et nous ne sommes pas autorisés à le déplacer plus tard. L'objectif est d'avoir autant de chiffres que possible (dans l'attente) dans leur emplacement correct dans le tableau final. L'emplacement correct est défini comme l'emplacement où il apparaîtrait si les nombres étaient triés.

Que sait-on de ce problème? Quel est le taux de réussite le plus attendu et quel algorithme l'atteint?

_Remarques:

• _{Une question connexe est: Quel est l'algorithme de tri en ligne le plus rapide? . Il traite d'une situation dans laquelle les articles peuvent être déplacés à l'arrivée de nouveaux articles, et l'objectif est de minimiser le temps d'exécution.}

• _{Je suis principalement intéressé à maximiser le nombre attendu des positions correctes. Cependant, il est également intéressant s'il existe un moyen d'améliorer la probabilité que tous les nombres soient dans la bonne position, au-dessus de O (1 / N!)}