Tri le plus rapide possible

Bonjour à tous,

Tout d'abord merci de votre aide et de votre patience.
J'ai trouvé sur le forum de nombreux algorithmes de tris, et jusqu'à maintenant j'utilisais un tri par positions. Seulement ma fonction de tri est associée à du graphique, et elle ralentie considérablement mon traitement lorsque j'ai trop de points.

Après réflexion, j'ai réussi à décomposer mon problème, et maintenant je suis sûr de n'ajouter qu'un point à la fois (à la fin). Voici un exemple de série de chiffres:

Code:

---

0 10 20 30....5050 15

---

Ma question c'est comment obtenir:

Code:

---

0 10 15 20 30.... 5050

---

le plus rapidement possible?

Merci, @+.

Si tu peux te contenter d'un O(n) pour la recherche de l'emplacement auquel insérer le nouvel élément, l'utilisation d'une liste chaînée est le plus rapide pour l'insertion puisqu'elles ne nécessitent pas de décaler d'éléments, et est relativement simple à mettre en oeuvre.
Sinon, tu peux utiliser une structure d'arbre (arbre binaire de recherche par exemple). Il y a peut-être mieux ?

Bonjour,

je suppose que tu dois ajouter un élément TRES souvent !!!
Même si la complexité pour la recherche est linéraire, le fait de rajouter un élément à chaque fois rend la compléxité globale élevé.
En revanche, un tri fait exactement cela de manière intélligente : le tri par tas !!!
Il est en O(nLogn).

Effectivement j'ajoute très souvent des éléments...
Donc, après réflexion je me suis effectivement lancer dans un algorythme de tri par tas..J'ai trouvé pas mal de doc, mais si je galère je vous recontact. ;)

Merci bocoup,
@+.

Si les valeurs que tu veux trier sont dans une plage "raisonnable" 1..k (et donc un n raisonnable), tu peux trier en un temps O(n), par un tri postal.

Sinon, peut être qu'en utilisant et en maintenant une structure d'arbre binaire tu pourrais arriver à quelque chose d'interressant

En effet, pour obtenir tes valeurs dans l'ordre tu effectues un parcours infixe (à gauche ou à droite suivant l'organisation de ton ABR), ce qui s'effectue dans un temps linéaire. Ensuite, lorsque tu veux insérer un élément, cela se fait en O(ln n) en moyenne.