Introsort (Ordenación introspectiva) mediante punteros de función - librería para MetaTrader 5

Ordenación Introspectiva

Esta es una versión revisada de la librería Introsort original, ahorala función Introsort() acepta un puntero opcional a una función de comparación personalizada.

Intro o ordenación introspectiva es un algoritmo de ordenación híbrido que proporciona un rendimiento rápido. Es un algoritmo de ordenación por comparación basado en tres fases. Utiliza la ordenación quicksort junto con los algoritmos heapsort e insertion-sort.

Ordenaciónrápida
La ordenación rápida es un algoritmo de divide y vencerás que funciona seleccionando un elemento pivote en la matriz y, a continuación, divide los demás elementos en dos submatrices comprobando si los elementos son mayores o menores. Por término medio, la ordenación rápida alogirthm tarda O(nlog(n)), con una complejidad en el peor de los casos de O(ⁿ²).

Heap Sort
Heap sort algoirthm es un método de ordenación basado en comparaciones binarias. Es un algoritmo de ordenación inestable con una complejidad de tiempo en el peor caso y en el caso medio de O(nlog(n)), y una complejidad de tiempo en el mejor caso de O(n).

Ordenación porinserción
El algoritmo de ordenación por inserción es un método de ordenación sencillo que construye la matriz ordenada final de un elemento cada vez. Su complejidad temporal en el peor caso y en el caso medio es O(ⁿ²) y en el mejor caso es O(n).

El algoritmo Introsort combina las partes buenas de estos tres algoritmos. Comienza con la ordenación rápida, cambiando a la ordenación heapsort cuando la profundidad de la recursión supera un nivel basado en el número de elementos que comienzan a ordenarse y cambia a la ordenación por inserción cuando el número de elementos es inferior a algún valor umbral.

• Si el tamaño de la partición es tal que existe la posibilidad de superar el límite máximo de profundidad, Introsort cambia a Heapsort.
• Si el tamaño de la partición es demasiado pequeño entonces Quicksort cambia a Insertion Sort.
• Si el tamaño de la partición está por debajo del límite y no es demasiado pequeño, entonces realiza un simple quicksort.

Introsort tiene un comportamiento en tiempo de ejecución particularmente bueno. Es uno de los algoritmos de ordenación por comparación más rápidos que se utilizan en la actualidad, y es la implementación habitual del algoritmo std::sort que se proporciona con la STL de C++, la biblioteca de clases de Microsoft .NET Framework, la biblioteca estándar de C++ de GNU y la biblioteca libc++ de LLVM.

//+------------------------------------------------------------------+
//| Introsort|
//+------------------------------------------------------------------+
/**
 * Ordena el array de entrada in situ usando la función de comparación less.
 * Puede especificar su propia función de comparación. Si no se especifica ninguna función
 *, se utilizará una ordenación ascendente.
 */
template<typename T>
void Introsort(T &arr[]);

//+------------------------------------------------------------------+
//| Introsort usando un puntero a la función personalizada Less(). ||
//| Una función personalizada Less() toma dos argumentos y contiene lógica ||
//| para decidir su orden relativo en el array ordenado. La idea es
//| proporcionar flexibilidad para que Introsort() se pueda utilizar para cualquier |
//| tipo (incluyendo tipos definidos por el usuario como objetos o estructuras) ||
//| y se puede utilizar para obtener cualquier orden de clasificación deseado (ascendente, |
//| orden descendente o personalizado de los campos de la estructura). ||
//+------------------------------------------------------------------+
template<typename T, typename LessFunc>
void Introsort(T &arr[], LessFunc pfnLess);

Función de comparación Menos:

bool MyLessFunc(const MyStruct &x, const MyStruct &y)
  {
//--- ordenar por A (ascendente)
   if(x.A < y.A) return(true);
   if(x.A > y.A) return(false);

//--- si igual en A, ordenar por B (ascendente)
   if(x.B < y.B) return(true);
   if(x.B > y.B) return(false);

//--- si igual en B, ordenar por C (ascendente)
   if(x.C < y.C) return(true);
   if(x.C > y.C) return(false);

//--- todas las claves son iguales
   return(false);
  }


// Definir un tipo de puntero a la función personalizada Less.
typedef bool (*pLess)(const MyStruct &x, const MyStruct &y);


// Ordenar array de estructuras usando función Less personalizada.
Introsort(structArray, (pLess)MyLessFunc);