Quel algorithme pour insertion d'objets "triés" da

Bsr,

J'ai un TList dans laquelle je souhaite ajouter n Objects. (avec n < 100000 soyons raisonnable)

Ces objets possèdent une propriété ID (elle même composée de x champs mais peu importe).
Je ne désire pas retrouver les objets par leur index, ni leur adresse, mais bien par leur ID.

J'aimerais insérer ces objets dans ma liste de telle sorte qu'ils
soient en permanance triés sur leur ID.

Quel algorithme utiliser pour retrouver l'index d'insertion mais aussi la position d'un objet tant qu'on y est ?


D'autre part l'emploi d'une liste est-il judicieux ?

Sur le net plusieurs sites parlent d'arbre binaire équilibré ?
Comment ca marche et de quoi s'agit-il exactement ?

Merci

@+
Php

Déjà une TList de base ne suffit par car on doit coder pour inserer l'objet à la bonne place. Dans un liste triée on travaille par dichotomie.

Si tu connais le nombre d'objet à l'avance, tu peux spécifier la Capacity de la tlist au départ, cela évitera les realloctions mémoire.

J'aurai tendance à dire qu'un arbre binaire est plus performant, mais il faudrait le tester (surtout si tu ne connais pas le nombre d'objet au préalable).

Pour ce qui est des algo, un tour dans google devrait faire l'affaire.

utilise plutot une Tstringlist si votreID de type string si non converti le enstring avec une lengeur fixe en ajoutant des 0 au début:
pax example 1-->00001, 2--->00002, et insi de suite ,
tstringlist a une otion qui trie les odnnées entrée, pour le réste de tes odnnée tu peut les ajouter normalement comme dans une Tlist avec

Code:

---

1 2 3 4 5 6 7 8

var t:^votrerecord; begin new(t); t.id:=4; .... TStringList.additem(formatFloat('000000',t.id),object(t));// a vérifier end;

---

Bjr,

Merci,

J'ai donc au final utilisé la dichotomie et ca marche tès bien sur 10 000 items !

A condition de penser à retrier ma liste dès que l'ID d'un objet est modifié. :twisted:

Pour les arbres binaires je verrais plus tard.


@+
Php