Ajout d'éléments à un tableau trié

Quel serait le moyen le plus rapide de le faire (d'un point de vue algorithmique et pratique)?

Je pensais à quelque chose dans le sens suivant.

Je pourrais ajouter à la fin d'un tableau, puis utiliser des bullesort car il a un meilleur cas (tableau totalement trié au début) qui est proche de cela, et a un temps d'exécution linéaire (dans le meilleur des cas).

D'un autre côté, si je sais que je commence avec un tableau trié, je peux utiliser une recherche binaire pour trouver le point d'insertion d'un élément donné.

Mon intuition est que la deuxième façon est presque optimale, mais curieuse de voir ce qui existe.

Comment le faire au mieux?

Nous comptons le nombre de lectures et d'écritures d'éléments de tableau. Pour faire du tri à bulles, vous avez besoin de accès (l'écriture initiale jusqu'à la fin, puis, dans le pire des cas, deux lectures et deux écritures pour effectuer n échanges). Pour faire la recherche binaire, nous avons besoin de 2 log n + 2 n + 1 ( 2 log n pour la recherche binaire, puis, dans le pire des cas, 2 n pour décaler les éléments du tableau vers la droite, puis 1 pour écrire l'élément du tableau dans sa position correcte).$1 + 4n$$n$$2\log n + 2n + 1$$2\log n$$2n$

Ainsi, les deux méthodes ont la même complexité pour les implémentations de tableaux, mais la méthode de recherche binaire nécessite moins d'accès aux tableaux à long terme ... asymptotiquement, deux fois moins. Il y a naturellement d'autres facteurs en jeu.

En fait, vous pouvez utiliser de meilleures implémentations et ne compter que les accès réels aux tableaux (pas les accès à l'élément à insérer). Vous pouvez faire pour le tri à bulles et enregistrer n + 2 n + 1 pour la recherche binaire ... donc si l'accès au registre / cache est bon marché et l'accès au tableau est cher, la recherche depuis la fin et le déplacement en cours de route (plus intelligent tri à bulles pour l'insertion) pourrait être mieux, mais pas asymptotiquement.$2n + 1$$\log n + 2n + 1$

Une meilleure solution pourrait impliquer l'utilisation d'une structure de données différente. Les tableaux vous donnent des accès O (1) (accès aléatoire), mais les insertions et les suppressions peuvent coûter cher. Une table de hachage pourrait avoir O (1) insertions et suppressions, les accès coûteraient. D'autres options incluent les BST et les tas, etc. Il pourrait être utile de considérer les besoins d'utilisation de votre application pour l'insertion, la suppression et l'accès, et choisissez une structure plus spécialisée.

Notez également que si vous souhaitez ajouter éléments à un tableau trié de n éléments, une bonne idée pourrait être de trier efficacement les m éléments, puis de fusionner les deux tableaux; aussi, les tableaux triés peuvent être construits efficacement en utilisant par exemple des tas (tri par tas).$m$$n$$m$

Si vous avez une raison quelconque de ne pas utiliser le segment de mémoire, envisagez d'utiliser le tri par insertion au lieu du tri par bulle. C'est mieux quand vous avez quelques éléments non triés.

Parce que vous utilisez un tableau, il en coûte pour insérer un élément - lorsque vous ajoutez quelque chose au milieu d'un tableau, par exemple, vous devez déplacer tous les éléments après lui de sorte que le tableau reste trié .$O(n)$

Le moyen le plus rapide pour savoir où placer l'élément est comme vous l'avez mentionné, une recherche binaire, qui est , donc la complexité totale va être O ( n + lg n ) , qui est de l'ordre de O ( n ) .$O(\lg n)$$O(n + \lg n)$$O(n)$

$O(1)$

Quoi qu'il en soit, je ne vois aucune raison de supprimer le problème des bulles pour ce problème.

Patrick87 a très bien expliqué tout cela. Mais une optimisation supplémentaire que vous pourriez faire serait d'utiliser quelque chose comme un tampon circulaire: vous pouvez déplacer les éléments à droite de la position de l'élément inséré vers la droite, comme d'habitude. Mais vous pouvez également déplacer des éléments vers la gauche de la position correcte vers la gauche. Pour ce faire, vous devez traiter le tableau comme circulaire, c'est-à-dire que le dernier élément est juste avant le premier et il vous oblige également à conserver l'index où les éléments commencent actuellement.

Si vous faites cela, cela pourrait signifier que vous effectuez environ la moitié du nombre d'accès aux tableaux (en supposant une distribution uniforme des index dans lesquels vous insérez). Dans le cas d'une recherche binaire pour trouver la position, il est trivial de choisir de passer à gauche ou à droite. Dans le cas du tri à bulles, vous devez «deviner» correctement avant de commencer. Mais cela est simple: il suffit de comparer l'élément inséré avec la médiane du tableau, ce qui peut être fait en accès unique au tableau.

J'ai utilisé l' algorithme de tri par insertion efficacement pour ce problème. À un moment donné, nous avons eu un problème de performances avec un objet de table de hachage, j'ai écrit un nouvel objet qui utilisait la recherche binaire à la place, ce qui augmentait considérablement les performances. Pour conserver la liste triée, il conserverait une trace du nombre d'éléments ajoutés depuis le dernier tri (c'est-à-dire le nombre d'éléments non triés), lorsque la liste devait être triée en raison d'une demande de recherche, elle effectuait un tri par insertion ou un tri rapide selon sur le pourcentage d'articles non triés. L'utilisation du tri par insertion a été essentielle pour améliorer les performances.