Meilleure façon de trier un tableau

Question

Dites que j'ai un tableau d'enregistrements que je veux trier en fonction de l'un des champs de l'enregistrement. Quel est le meilleur moyen d'y parvenir?

TExample = record 
    SortOrder : integer; 
    SomethingElse : string; 
end; 

var SomeVar : array of TExample; 

Answer 1

Vous pouvez ajouter des pointeurs aux éléments du tableau à TList, puis appeler TList.Sort avec une fonction de comparaison, et enfin créer un nouveau tableau et copier les valeurs hors de TList dans l'ordre souhaité.

Cependant, si vous utilisez la version suivante, D2009, il y a une nouvelle bibliothèque de collections qui peuvent trier les tableaux. Il faut une implémentation optionnelle IComparer<TExample> pour les ordres de tri personnalisés. Ici, il est en action pour votre cas particulier:

TArray.Sort<TExample>(SomeVar , TDelegatedComparer<TExample>.Construct(
    function(const Left, Right: TExample): Integer 
    begin 
    Result := TComparer<Integer>.Default.Compare(Left.SortOrder, Right.SortOrder); 
    end)); 

Answer 2

Utilisez l'une des alorithms de tri proposent par Wikipedia. La fonction de permutation doit permuter les éléments du tableau en utilisant une variable temporaire du même type que les éléments du tableau. Utilisez un tri stable si vous voulez que les entrées ayant la même valeur entière SortOrder restent dans l'ordre où elles se trouvaient en premier lieu.

Answer 3

Avec un tableau, j'utiliser soit quicksort ou peut-être heapsort, et il suffit de changer la comparaison à utiliser TExample.SortOrder, la partie swap va encore agir seulement sur les pointeurs de tableau et d'échange. Si le tableau est très grand, vous pouvez avoir besoin d'une structure de liste liée s'il y a beaucoup d'insertion et de suppression.

routines à base C, il y a plusieurs ici http://www.yendor.com/programming/sort/

Un autre site, mais a la source pascals http://www.dcc.uchile.cl/~rbaeza/handbook/sort_a.html

Answer 4

Si votre besoin triée par chaîne, puis utiliser triée TStringList et Ajouter un enregistrement par TString.AddObject(string, Pointer(int_val)).

Mais si besoin tri par champ entier et chaîne - utilisez TObjectList et après avoir ajouté tous les enregistrements, appelez TObjectList.Sort avec les fonctions triées nécessaires en tant que paramètre.

Answer 5

TStringList ont une méthode de tri efficace.
Si vous souhaitez trier, utilisez un objet TStringList avec la propriété Sorted sur True.

NOTE: Pour plus de vitesse, ajouter des objets dans un rapport Pas de classement TStringList et à la fin changer la propriété sur True.
REMARQUE: Pour le tri par champ entier, convertissez en chaîne.
REMARQUE: S'il existe des valeurs en double, cette méthode n'est pas valide.

Cordialement.

Answer 6

Tout dépend du nombre d'enregistrements que vous triez. Si vous ne faites que trier moins de quelques centaines, alors les autres méthodes de tri fonctionnent bien, si vous allez trier plus, alors jetez un oeil à l'ancien projet fiable de Turbo Power SysTools. Il y a un très bon algorithme de tri inclus dans la source. Celui qui fait un très bon travail de tri des millions de dossiers d'une manière efficace.

Si vous souhaitez utiliser la méthode tStringList pour trier une liste d'enregistrements, assurez-vous que votre entier est complété à droite avant de l'insérer dans la liste. Vous pouvez utiliser le format ('% .10d', [rec.sortorder]) à droite aligner à 10 chiffres par exemple.

Answer 7

(je sais que c'est un an plus tard, mais toujours des choses utiles.)

suggestion Skamradt aux valeurs entières de pad suppose que vous allez trier en utilisant une comparaison de type chaîne. Ce serait lent. Appel de format() pour chaque insertion, plus lent encore. Au lieu de cela, vous voulez faire une comparaison entière.

Vous commencez avec un type d'enregistrement:

TExample = record 
    SortOrder : integer; 
    SomethingElse : string; 
end; 

Vous ne précisait pas comment les documents ont été stockés, ou comment vous vouliez y accéder une fois triés. Alors supposons que vous les mettez dans un tableau dynamique:

var MyDA Array of TExample; 
... 
    SetLength(MyDA,NewSize);   //allocate memory for the dynamic array 
    for i:=0 to NewSize-1 do begin  //fill the array with records 
    MyDA[i].SortOrder := SomeInteger; 
    MyDA[i].SomethingElse := SomeString; 
    end; 

Maintenant, vous voulez trier ce tableau par la valeur entière SortOrder. Si ce que vous voulez sortir est un TStringList (vous pouvez donc utiliser la méthode ts.Find) alors vous devez ajouter chaque chaîne à la liste et ajouter le SortOrder comme un pointeur. Puis trier sur le pointeur:

var tsExamples: TStringList;   //declare it somewhere (global or local) 
... 
    tsExamples := tStringList.create; //allocate it somewhere (and free it later!) 
... 
    tsExamples.Clear;     //now let's use it 
    tsExamples.sorted := False;   //don't want to sort after every add 
    tsExamples.Capacity := High(MyDA)+1 //don't want to increase size with every add 
             //an empty dynamic array has High() = -1 
    for i:=0 to High(MyDA) do begin 
    tsExamples.AddObject(MyDA[i].SomethingElse,TObject(MyDA[i].SortOrder)); 
    end; 

Notez le tour de la coulée entier SortOrder en un pointeur TObject, qui est stocké dans la propriété TStringList.Object. (Cela dépend du fait que Integer et pointeur sont de la même taille.) Quelque part, nous devons définir une fonction pour comparer les pointeurs de TObject:

function CompareObjects(ts:tStringList; Item1,Item2: integer): Integer; 
var i,j: integer; 
begin 
    Result := integer(ts.Objects[i]) - integer(ts.Objects[j]; 
end; 

Maintenant, nous pouvons trier les tsList sur .object en appelant .CustomSort place de .Sort (qui trierait sur la valeur de chaîne.)

tsExample.CustomSort(@CompareObjects);  //Sort the list 

le TStringList est triée par ordre, de sorte que vous pouvez itérer dessus de 0 à .Count-1 et lire les chaînes dans l'ordre.

Mais supposons que vous ne vouliez pas de TStringList, juste un tableau dans l'ordre trié. Ou les enregistrements contiennent plus de données que juste une chaîne dans cet exemple, et votre ordre de tri est plus complexe. Vous pouvez ignorer l'étape d'ajout de chaque chaîne et ajouter simplement l'index du tableau en tant qu'éléments dans un TList. Faites tout ce qui précède la même manière, à l'exception d'utiliser un TList au lieu de TStringList:

var Mlist: TList;     //a list of Pointers 
... 
    for i:=0 to High(MyDA) do 
    Mlist.add(Pointer(i));  //cast the array index as a Pointer 
    Mlist.Sort(@CompareRecords); //using the compare function below 

function CompareRecords(Item1, Item2: Integer): Integer; 
var i,j: integer; 
begin 
    i := integer(item1);   //recover the index into MyDA 
    j := integer(item2);   // and use it to access any field 
    Result := SomeFunctionOf(MyDA[i].SomeField) - SomeFunctionOf(MyDA[j].SomeField); 
end; 

Maintenant que Activer ListeM est triée, l'utiliser comme une table de recherche pour accéder au tableau dans l'ordre de tri:

for i:=0 to Mlist.Count-1 do begin 
    Something := MyDA[integer(Mlist[i])].SomeField; 
    end; 

Comme je itère sur le TList, nous récupérons les index de tableau dans l'ordre trié. Nous avons juste besoin de les renvoyer aux entiers, puisque le TList pense qu'ils sont des pointeurs. J'aime faire cela de cette façon, mais vous pouvez aussi mettre de vrais pointeurs sur les éléments du tableau dans TList en ajoutant l'adresse de l'élément tableau au lieu de son index. Ensuite, pour les utiliser, vous les transformerez en pointeurs vers des enregistrements TExample. C'est ce que Barry Kelly et CoolMagic ont dit de faire dans leurs réponses.

Answer 8

L'algorithme quicksort est souvent utilisé lorsqu'un tri rapide est requis. Delphi est (ou était) l'utiliser pour List.Sort par exemple. La liste Delphi peut être utilisée pour trier n'importe quoi, mais c'est un conteneur lourd, qui est censé ressembler à un tableau de pointeurs sur les structures. C'est lourd même si on utilise des trucs comme Guy Gordon dans ce fil (Putting index ou quoi que ce soit à la place des pointeurs, ou mettre directement des valeurs si elles sont plus petites que 32 bits): il faut construire une liste et ainsi de suite ...

Par conséquent, une alternative pour facilement et rapidement trier un tableau de struct pourrait être d'utiliser qsort C runtime function de msvcrt.dll.

Voici une déclaration qui pourrait être bonne (Attention: code portable sur Windows uniquement).

type TComparatorFunction = function(lpItem1: Pointer; lpItem2: Pointer): Integer; cdecl; 
procedure qsort(base: Pointer; num: Cardinal; size: Cardinal; lpComparatorFunction: TComparatorFunction) cdecl; external 'msvcrt.dll'; 

Exemple complet here.

Notez que le tri direct du tableau d'enregistrements peut être lent si les enregistrements sont volumineux. Dans ce cas, le tri d'un tableau de pointeurs vers les enregistrements peut être plus rapide (d'une manière ou d'une autre comme l'approche de liste).

Answer 9

J'ai créé un exemple très simple qui fonctionne correctement si le champ de tri est une chaîne.

Type 
    THuman = Class 
    Public 
    Name: String; 
    Age: Byte; 
    Constructor Create(Name: String; Age: Integer); 
    End; 

Constructor THuman.Create(Name: String; Age: Integer); 
Begin 
    Self.Name:= Name; 
    Self.Age:= Age; 
End; 

Procedure Test(); 
Var 
Human: THuman; 
Humans: Array Of THuman; 
List: TStringList; 
Begin 

SetLength(Humans, 3); 
Humans[0]:= THuman.Create('David', 41); 
Humans[1]:= THuman.Create('Brian', 50); 
Humans[2]:= THuman.Create('Alex', 20); 

List:= TStringList.Create; 
List.AddObject(Humans[0].Name, TObject(Humans[0])); 
List.AddObject(Humans[1].Name, TObject(Humans[1])); 
List.AddObject(Humans[2].Name, TObject(Humans[2])); 
List.Sort; 

Human:= THuman(List.Objects[0]); 
Showmessage('The first person on the list is the human ' + Human.name + '!'); 

List.Free; 
End; 

Answer 10

Si vous avez Delphi XE2 ou plus récent, vous pouvez essayer:

var 
    someVar: array of TExample; 
    list: TList<TExample>; 
    sortedVar: array of TExample; 
begin 
    list := TList<TExample>.Create(someVar); 
    try 
    list.Sort; 
    sortedVar := list.ToArray; 
    finally 
    list.Free; 
    end; 
end;