Introsort (classificação introspectiva) usando ponteiros de função - biblioteca para MetaTrader 5

Classificação introspectiva

Esta é uma versão revisada da biblioteca Introsort original, agoraa função Introsort() aceita um ponteiro de função opcional para a função de comparação personalizada.

A classificação Intro ou Introspective é um algoritmo de classificação híbrido que oferece desempenho rápido. É um algoritmo de classificação baseado em comparação e em três fases. Ele usa a classificação quicksort junto com os algoritmos heapsort e insertion-sort.

Quick Sort
O Quick Sort é um algoritmo de divisão e conquista que funciona selecionando um elemento pivô na matriz e, em seguida, particiona os outros elementos em duas subvariedades, verificando se os elementos são maiores ou menores. Em média, o algoritmo de classificação rápida leva O(nlog(n)) tempo, com a complexidade do pior caso de O(ⁿ²).

Heap Sort
Heap sort algoirthm é um método de classificação baseado em comparação de heap binário. É um algoritmo de classificação instável com complexidade de tempo no pior caso e no caso médio de O(nlog(n)), e complexidade de tempo no melhor caso de O(n).

Classificação porinserção
O algoritmo de classificação por inserção é um método de classificação simples que constrói a matriz classificada final um item por vez. Sua complexidade de tempo para o pior caso e o caso médio é O(ⁿ²) e o melhor caso é O(n).

O algoritmo Introsort combina as partes boas desses três algoritmos. Ele começa com a classificação rápida, mudando para a classificação heapsort quando a profundidade da recursão excede um nível baseado no número de elementos que começam a ser classificados e muda para a classificação de inserção quando o número de elementos é menor que algum valor limite.

• Se o tamanho da partição for tal que exista a possibilidade de exceder o limite máximo de profundidade, o Introsort mudará para Heapsort.
• Se o tamanho da partição for muito pequeno, o Quicksort mudará para Insertion Sort.
• Se o tamanho da partição estiver abaixo do limite e não for muito pequeno, ele executará um quicksort simples.

O Introsort tem um comportamento particularmente bom em tempo de execução. É um dos algoritmos de classificação de comparação mais rápidos em uso atualmente e é a implementação usual do algoritmo std::sort fornecido com o C++ STL, Microsoft .NET Framework Class Library, biblioteca GNU Standard C++ e biblioteca LLVM libc++.

//+------------------------------------------------------------------+
//| Introsort|
//+------------------------------------------------------------------+
/**
 * Classifique a matriz de entrada no local usando a função de comparação less.
 * Você pode especificar sua própria função de comparação. Se nenhuma função for
 * especificada, será usada a classificação ascendente.
 */
template<typename T>
void Introsort(T &arr[]);

//+------------------------------------------------------------------+
//| Introspecção usando um ponteiro para a função Less() personalizada.
//| Uma função Less() personalizada recebe dois argumentos e contém lógica.
//| para decidir sua ordem relativa no array classificado. A ideia é
//| Para oferecer flexibilidade, de modo que Introsort() possa ser usado para qualquer |
//| tipo (incluindo tipos definidos pelo usuário, como objetos ou estruturas)
//| e pode ser usado para obter qualquer ordem de classificação desejada (ascendente, |
//| Ordem decrescente ou personalizada dos campos da estrutura).
//+------------------------------------------------------------------+
template<typename T, typename LessFunc>
void Introsort(T &arr[], LessFunc pfnLess);

Função de comparação Menos:

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

//--- se igual em A, classificar por B (asc)
   if(x.B < y.B) return(true);
   if(x.B > y.B) return(false);

//--- se for igual em B, classificar por C (ascendente)
   if(x.C < y.C) return(true);
   if(x.C > y.C) return(false);

//--- todas as chaves são iguais
   return(false);
  }


// Definir um tipo de ponteiro para a função Less personalizada.
typedef bool (*pLess)(const MyStruct &x, const MyStruct &y);


// Ordenar matriz de estruturas usando a função Less personalizada.
Introsort(structArray, (pLess)MyLessFunc);