Meilleure façon de trier un tableau
https://stackoverflow.com/questions/41733
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Supposons que j'ai un tableau d'enregistrements que je souhaite trier en fonction de l'un des champs de l'enregistrement.Quelle est la meilleure façon d’y parvenir ?
TExample = record
SortOrder : integer;
SomethingElse : string;
end;
var SomeVar : array of TExample;
La solution
Vous pouvez ajouter des pointeurs vers les éléments du tableau dans un TList, puis appelle TList.Sort avec une fonction de comparaison, et enfin créez un nouveau tableau et copiez les valeurs hors de la TList dans l'ordre souhaité.
Cependant, si vous utilisez la prochaine version, D2009, il existe une nouvelle bibliothèque de collections capable de trier les tableaux.Il faut une option IComparer<TExample> mise en œuvre d’ordres de tri personnalisés.Le voici en action pour votre cas spécifique :
TArray.Sort<TExample>(SomeVar , TDelegatedComparer<TExample>.Construct(
function(const Left, Right: TExample): Integer
begin
Result := TComparer<Integer>.Default.Compare(Left.SortOrder, Right.SortOrder);
end));
Autres conseils
(Je sais que c'est un an plus tard, mais c'est toujours utile.)
La suggestion de Skamradt de compléter les valeurs entières suppose que vous allez trier à l'aide d'une comparaison de chaînes.Ce serait lent.Appel de format() pour chaque insertion, encore plus lent.Au lieu de cela, vous souhaitez effectuer une comparaison d’entiers.
Vous commencez avec un type d'enregistrement :
TExample = record
SortOrder : integer;
SomethingElse : string;
end;
Vous n'avez pas indiqué comment les enregistrements étaient stockés ni comment vous souhaitiez y accéder une fois triés.Supposons donc que vous les placiez 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;
Vous souhaitez maintenant trier ce tableau selon la valeur entière SortOrder.Si ce que vous voulez est un TStringList (vous pouvez donc utiliser la méthode ts.Find), vous devez alors ajouter chaque chaîne à la liste et ajouter le SortOrder comme pointeur.Triez ensuite 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 l'astuce consistant à convertir Integer SortOrder en un pointeur TObject, qui est stocké dans la propriété TStringList.Object.(Cela dépend du fait que Integer et Pointer ont la même taille.) Quelque part, nous devons définir une fonction pour comparer les pointeurs 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 la tsList sur .Object en appelant .CustomSort au lieu de .Sort (ce qui trierait sur la valeur de la chaîne.)
tsExample.CustomSort(@CompareObjects); //Sort the list
La TStringList est maintenant triée, vous pouvez donc la parcourir de 0 à .Count-1 et lire les chaînes dans l'ordre trié.
Mais supposons que vous ne vouliez pas de TStringList, juste un tableau trié.Ou encore, les enregistrements contiennent plus de données que la seule chaîne de cet exemple et votre ordre de tri est plus complexe.Vous pouvez ignorer l'étape d'ajout de chaque chaîne et simplement ajouter l'index du tableau en tant qu'éléments dans une TList.Faites tout ce qui précède de la même manière, sauf utilisez 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 Mlist est trié, utilisez-le comme table de recherche pour accéder au tableau dans l'ordre trié :
for i:=0 to Mlist.Count-1 do begin
Something := MyDA[integer(Mlist[i])].SomeField;
end;
Au fur et à mesure que je parcourt la TList, nous récupérons les index du tableau dans l'ordre trié.Nous avons juste besoin de les reconvertir en nombres entiers, puisque la TList pense que ce sont des pointeurs.
J'aime procéder de cette façon, mais vous pouvez également placer de vrais pointeurs vers des éléments du tableau dans la TList en ajoutant l'adresse de l'élément du tableau au lieu de son index.Ensuite, pour les utiliser, vous les convertirez en pointeurs vers des enregistrements TExample.C'est ce que Barry Kelly et CoolMagic ont dit de faire dans leurs réponses.
Si vous avez besoin d'être trié par chaîne, utilisez trié TStringList et ajouter un enregistrement par TString.AddObject(string, Pointer(int_val)).
Mais si besoin, trier 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 comme paramètre.
Tout dépend du nombre d'enregistrements que vous triez.Si vous ne triez que moins de quelques centaines, les autres méthodes de tri fonctionnent bien. Si vous souhaitez trier davantage, jetez un œil à l'ancien fidèle Turbo Power. Outils système projet.Il existe un très bon algorithme de tri inclus dans la source.Celui qui fait un très bon travail en triant des millions d’enregistrements de manière efficace.
Si vous envisagez d'utiliser la méthode tStringList pour trier une liste d'enregistrements, assurez-vous que votre entier est complété vers la droite avant de l'insérer dans la liste.Vous pouvez utiliser le format('%.10d',[rec.sortorder]) pour aligner à droite sur 10 chiffres par exemple.
L'algorithme de tri rapide est souvent utilisé lorsqu'un tri rapide est requis.Delphi l'utilise (ou l'utilisait) pour List.Sort par exemple.Delphi List peut être utilisé pour trier n'importe quoi, mais il s'agit d'un conteneur lourd, censé ressembler à un tableau de pointeurs sur des structures.C'est lourd même si on utilise des astuces comme Guy Gordon dans ce fil (Mettre un index ou quoi que ce soit à la place des pointeurs, ou mettre directement des valeurs si elles sont inférieures à 32 bits) :nous devons construire une liste et ainsi de suite...
Par conséquent, une alternative pour trier facilement et rapidement un tableau de structures pourrait être d'utiliser fonction d'exécution qsort C à partir de msvcrt.dll.
Voici une déclaration qui pourrait être bonne (Attention :code portable sous 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 ici.
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 (en quelque sorte comme l'approche List).
Avec un tableau, j'utiliserais soit quicksort ou éventuellement heapsort, et changez simplement la comparaison pour utiliser TExample.SortOrder, la partie swap va toujours agir simplement sur le tableau et échanger les pointeurs.Si le tableau est très grand, vous souhaiterez peut-être une structure de liste chaînée s'il y a beaucoup d'insertions et de suppressions.
Routines basées sur C, il y en a plusieurs icihttp://www.yendor.com/programming/sort/
Un autre site, mais qui a une source pascalehttp://www.dcc.uchile.cl/~rbaeza/handbook/sort_a.html
Utilisez un des algorithmes de tri proposés par Wikipédia.La fonction Swap doit échanger 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 souhaitez que les entrées avec la même valeur entière SortOrder restent dans l’ordre dans lequel elles se trouvaient en premier lieu.
TStringList avoir une méthode de tri efficace.
Si vous voulez trier, utilisez un TStringList objet avec Sorted propriété à True.
NOTE:Pour plus de rapidité, ajoutez des objets dans un format non trié TStringList et à la fin, changez la propriété en True.
NOTE:Pour trier par champ entier, convertissez en chaîne.
NOTE:S'il existe des valeurs en double, cette méthode n'est pas valide.
Salutations.
Si vous disposez de Delphi XE2 ou d'une version plus récente, 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;
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;
