Fonction de tri array

Bonjour

J'ai déclaré ce nouveau type pour extraire les mots un fichier texte leurs positions le problème c'est le tri
comment je peux les triés

Code:

---

1 2 3 4 5 6 7 8 9

type TListDesMots = record LeMot : string; Sapos : cardinal; end;   Var ListDesMots:array[0..131071]of TListDesMots ;

---

j'ai cette fonction

Code:

---

1 2 3

SortArray(ListDesMots, 0, SizeOf(ListDesMots[Low(ListDesMots)]), 0,wcunt-1 , ComparePersons);

---

mais lorsque il s'agi de 80000 mots elle devient un peu lente et il y a ce message "Stack Overflow..."

Bonjour,

Pourquoi ne pas essayer de faire en sorte d'ajouter le mot à sa bonne place dans le tableau ?

Dans la logique on récupère le mot, on détermine l'indice où il devrait être avec une recherche dichotomique puis on insère le mot à l'indice prévu.

Bonjour
Cette recherche dichotomique peut trier les mot si le nombre et inconnu ?

Je ne suis pas sûr d'avoir bien compris la question mais la recherche dichotomique est une fonction de recherche pas de tri. Cependant dans mon idée on va utiliser cette recherche pour positionner "just in time" les enregistrement à leur bonne place dans le tableau au moment où l'on veut ajouter un nouvel enregistrement au tableau.

Peut-être que c'est la notion de recherche dichotomique que tu ne visualises pas, c'est en fait une autre méthode de recherche que celle linéaire mais qui nécessite de travailler sur un tableau trié au préalable. Fais une recherche dans google pour plus de détail sur son algorithme.

Merci je vais essayer le B-TREE

Salut,

Pour la recherche dichotomique suggérée par Aka Guymelef tu peux par exemple t'inspirer du code de la function IndexOfSL3(SL : TStringList; const S: string): Integer; qui se trouve ici (dans la 2ième moité du message du 21/07/2007, 15h15 ) : http://www.developpez.net/forums/sho...exofSL3&page=2
... il s'agit du code qu'on a trafficoté pour remplacer la function standard IndexOf pour gains de vitesse.
... mais attention il faudrait la remodeler :
- d'une part pour effectuer la recherche dans ta ListDesMots : array[0..131071]of TListDesMots (relativement simple);
- et d'autre part de sorte qu'elle renvoie l'Index de la bonne position d'un mot qui n'y figure pas encore (faut trouver une astuce)(*) car la fonction en son état actuel renvoie seulement l'index d'un mot qui y figure déjà.

A+ :D

EDIT du 8 mai : (*) : Comme l'idée d'Aka Guymelef consiste, me semble-t-il, à placer chaque nouveau mot à ajouter dans le tableau à l'index correspondant à sa bonne place lors et au fur et à mesure de la création du tableau de sorte que le tableau soit d'entrée de jeu toujours dans l'état trié, les modifications à apporter à IndexOfSL3 consistent :
- en une simplification : suppression de la partie if Not Sorted then ...
- et pour qu'elle renvoie l'Index de la bonne position d'un mot qui n'y figure pas encore il faudrait à première vue ajouter une variable Cprec: Integer qui mémorise la valeur prise lors du tour de boucle précédent par la variable C lors des comparaisons if SL[i] < S then C:=-1 else if SL[i] > S then C:=+1 else C:=0; et de détecter le moment où C change de signe (if C<>Cprec) et qui correspond à +/- 1 unité à la valeur de l'Index de la bonne position recherchée, puis pour savoir si cet index est égal à i, i+1 ou i-1 suffit de faire un test sur une liste d'une dizaine de mots pour effectuer le calibrage.

A+ :D

Re-Salut,

J'allais oublier : si tu veux trier un array de records qui est alimenté depuis un fichier qui n'est pas trié d'entrée de jeu au fur et à mesure de sa création(fichier provenant d'une appli tierce, par exemple), tu peux utiliser (*) la Function AlphaSortAOS( var A : ArrChaines; var PisteurClefs : ArrInteger; IgnoreCase : boolean) : boolean qui est encapsulée dans la procedure SupprDoublonsAOS(const nomFiSource, NomFiDest : string; IgnoreCase : boolean) et que tu peux trouver dans le message du 20/12/2007, 12h49 #61 qui se trouve ici : http://www.developpez.net/forums/sho...rt#post2784174
... la Function AlphaSortAOS est dérivée de la function de tri AlphaSort (on la trouve sur Google) plus rapide que QuickSort mais plus gourmand en mem-vive-disponible.

A+ :D

EDIT du 8 mai : (*) par "utiliser" la Function AlphaSortAOS je veux dire l'utiliser pour l'adapter à ton cas de figure en y remplaçant la var A : ArrChaines (array of string) par ton array de records et en y apportant les modifs qui découlent de ce remplacement.
.. Par contre tu également apporter ces mêmes modifs à la procedure SupprDoublonsAOS si tu veux profiter du tri pour éliminer les doublons susceptibles d'être présents.

A+ :D