Discussion :

[Ygster]

Salut,

J'hésite entre deux méthodes pour implémenter l'ajout, le tri et la suppression des doublons dans une matrice d'entiers. En fait je me demande laquelle est la plus performante en terme de rapidité (la mémoire n'est pas un problème vu le nombre d'éléments).

Méthode 1 :

Ajout de tous les éléments dans l'ordre où je les récupère, puis tri de la liste avec suppression des doublons.

Méthode 2 :

Tri et gestion des doublons au fur et à mesure de l'ajout d'éléments.


De plus je me demande quelle méthode de tri utiliser sachant que dans la plupart des cas je récupère une partie des éléments déjà triés.
Par exemple, je peux récupérer,
101 ; 102 ; 103 ; 104 ; 105
puis :
201 ; 202 ; 203 ; 204 ; 205
et enfin :
131 ; 132 ; 133 ; 134 ; 135

Je pense que le MergeSort serait bien indiqué dans ce cas puisqu'il fusionne des listes déjà triés mais j'aimerai bien une confirmation.

Voilà, si vous avez des idées, réponses ou pistes sur mes différentes questions.

Merci d'avance
Ygster

[Jedai]

Tu parles de matrices, mais j'ai plutôt l'impression que tu penses à des vecteurs ou même des listes ?

Une méthode particulièrement rapide pour gérer l'insertion d'un élément en maintenant la structure triée est d'utiliser un arbre binaire de recherche, ou éventuellement une de ses variantes équilibrées (arbre rouge-noir par exemple). Reste à voir dans quel langage tu travailles, dans quel cadre (est-ce le but de l'exercice ou peux tu employer une librairie toute faite par exemple), ...

--
Jedaï

[ToTo13]

Bonjour,

je pense également que tu as l'air de plutôt parler de vecteurs que de matrices.

En ce cas, il serait extremement utile de faire un tas. La maintenance du tas est en log(n), ce qui est avantageux et ça te permettra à tout moment de trier ton tableau.

[Jedai]

Les arbres rouge-noir sont néanmoins plus avantageux si tu veux avoir accès à ta liste triée en permanence, et le coût de l'insertion est en O(log n) également. Avec un tas, il t'en coûtera O(log n) à l'insertion, mais O(n log n) pour reconstituer le tableau trié à chaque fois que tu en auras besoin. (par contre les tas sont un peu plus facile à implémenter)

--
Jedaï

[Ygster]

Qu'est ce qui vous fait dire que je parle plutôt de liste que de matrice ? Pour l'instant en tout cas c'est bien codé sous la forme d'une matrice dynamique de x lignes et 3 colonnes dans mon programme.

Une méthode particulièrement rapide pour gérer l'insertion d'un élément en maintenant la structure triée est d'utiliser un arbre binaire de recherche, ou éventuellement une de ses variantes équilibrées (arbre rouge-noir par exemple). Reste à voir dans quel langage tu travailles, dans quel cadre (est-ce le but de l'exercice ou peux tu employer une librairie toute faite par exemple), ...

En fait dans la suite de mon programme je ne vais pas du tout utiliser le fait que le tableau soit trié à part pour l'affichage final (aucune recherche) donc je ne pense pas que l'arbre binaire de recherche soit vraiment utile. C'est pour ça que j'ai choisi une matrice.

Au niveau des contraintes je n'en ai quasiment aucune à part le langage (Delphi), c'est dans le cadre de mon job mais je peux installer à peu près ce que je veux.

En ce cas, il serait extremement utile de faire un tas. La maintenance du tas est en log(n), ce qui est avantageux et ça te permettra à tout moment de trier ton tableau.

Je viens de relire les articles de Wikipédia sur les tas et le tri par tas et je ne vois pas bien en quoi ça serait plus utile qu'un ABR dans mon cas.

En fait dans les solutions que vous proposez tous les 2, j'ai l'impression que ça va "compliquer" le parcours final pour l'affichage (avec la matrice il suffirait de faire un parcours séquenciel) mais je me trompe peut-être ?

Merci
Ygster