Introsort (tri introspectif) à l'aide de pointeurs de fonction - bibliothèque pour MetaTrader 5

Tri introspectif

Il s'agit d'une version révisée de la bibliothèque Introsort originale. Désormais,la fonction Introsort() accepte un pointeur de fonction optionnel vers une fonction de comparaison personnalisée.

Le tri Intro ou Introspective est un algorithme de tri hybride qui fournit des performances rapides. Il s'agit d'un algorithme de tri basé sur la comparaison, qui s'articule autour de trois phases. Il utilise le tri rapide ainsi que les algorithmes heapsort et insertion-sort.

Tri rapide
Le tri rapide est un algorithme de division et de conquête qui sélectionne un élément pivot dans le tableau, puis sépare les autres éléments en deux sous-réseaux en vérifiant si les éléments sont plus grands ou plus petits. En moyenne, le tri rapide prend O(nlog(n)) de temps, avec une complexité de O(ⁿ²) dans le pire des cas.

Tri en tas
L'algorithme de tri en tas est une méthode de tri basée sur une comparaison binaire en tas. Il s'agit d'un algorithme de tri instable dont la complexité temporelle dans le pire des cas et dans le cas moyen est de O(nlog(n)), et la complexité temporelle dans le meilleur des cas est de O(n).

Tri par insertion
L'algorithme de tri par insertion est une méthode de tri simple qui construit le tableau trié final un élément à la fois. Sa complexité temporelle dans le pire des cas et dans le cas moyen est de O(ⁿ²) et dans le meilleur des cas de O(n).

L'algorithme Introsort combine les avantages de ces trois algorithmes. Il commence par un tri rapide, passe à un tri en tas lorsque la profondeur de récursion dépasse un niveau basé sur le nombre d'éléments commencés à être triés et passe à un tri par insertion lorsque le nombre d'éléments est inférieur à une certaine valeur seuil.

• Si la taille de la partition est telle qu'il est possible de dépasser la limite de profondeur maximale, l'Introsort passe au Heapsort.
• Si la taille de la partition est trop petite, le tri sélectif passe au tri par insertion.
• Si la taille de la partition est inférieure à la limite et n'est pas trop petite, il effectue un simple tri sélectif.

L'Introsort se comporte particulièrement bien pendant l'exécution. C'est l'un des algorithmes de tri par comparaison les plus rapides utilisés aujourd'hui, et c'est l'implémentation habituelle de l'algorithme std::sort fourni avec la STL C++, la bibliothèque de classes Microsoft .NET Framework, la bibliothèque GNU Standard C++ et la bibliothèque LLVM libc++.

//+------------------------------------------------------------------+
//| Introsort|
//+------------------------------------------------------------------+
/**
 * Trier le tableau d'entrée sur place en utilisant la fonction de comparaison less.
 * Vous pouvez spécifier votre propre fonction de comparaison. Si aucune fonction n'est
 * spécifiée, le tri ascendant est utilisé.
 */
template<typename T>
void Introsort(T &arr[]);

//+------------------------------------------------------------------+
//| Introsort en utilisant un pointeur vers la fonction Less() personnalisée.
//| Une fonction Less() personnalisée prend deux arguments et contient de la logique |
//| pour décider de leur ordre relatif dans le tableau trié. L'idée est la suivante : |
//| pour apporter de la flexibilité afin que Introsort() puisse être utilisé pour n'importe quelle |
//| type (y compris les types définis par l'utilisateur tels que les objets ou les structures) |
//| et peut être utilisé pour obtenir n'importe quel ordre de tri souhaité (ascendant, ||).
//| ordre décroissant ou personnalisé des champs de la structure).
//+------------------------------------------------------------------+
template<typename T, typename LessFunc>
void Introsort(T &arr[], LessFunc pfnLess);

Fonction de comparaison Moins :

bool MyLessFunc(const MyStruct &x, const MyStruct &y)
  {
//--- trier par A (ascendant)
   if(x.A < y.A) return(true);
   if(x.A > y.A) return(false);

//--- si égal sur A, trier par B (ascendant)
   if(x.B < y.B) return(true);
   if(x.B > y.B) return(false);

//--- si égal sur B, trier par C (ascendant)
   if(x.C < y.C) return(true);
   if(x.C > y.C) return(false);

//--- toutes les clés sont égales
   return(false);
  }


// Définir un type de pointeur vers la fonction Less personnalisée.
typedef bool (*pLess)(const MyStruct &x, const MyStruct &y);


// Trier un tableau de structures à l'aide d'une fonction Less personnalisée.
Introsort(structArray, (pLess)MyLessFunc);