Интросортировка (интроспективная сортировка) с использованием функциональных указателей - библиотека для MetaTrader 5

Интроспективная сортировка

Это переработанная версия оригинальной библиотеки Introsort, теперьфункция Introsort() принимает необязательный указатель на пользовательскую функцию сравнения.

Intro или Introspective sort - это гибридный алгоритм сортировки, обеспечивающий высокую производительность. Это алгоритм сортировки на основе сравнения, основанный на трех фазах. В нем используется сортировка quicksort, а также алгоритмы heapsort и insertion-sort.

Быстрая сортировка
Быстрая сортировка - это алгоритм "разделяй и властвуй", который работает путем выбора центрального элемента в массиве, затем разбивает остальные элементы на два подмассива, проверяя условие, больше или меньше элементов. В среднем быстрая сортировка alogirthm занимает O(nlog(n)) времени, а в худшем случае сложность составляет O(ⁿ²).

Heap Sort
Heap sort algoirthm - это метод сортировки, основанный на сравнении бинарных куч. Это неустойчивый алгоритм сортировки с временной сложностью в худшем и среднем случае O(nlog(n)) и временной сложностью в лучшем случае O(n).

Алгоритмсортировки вставками
Алгоритм сортировки вставками - это простой метод сортировки, который строит окончательный отсортированный массив по одному элементу за раз. Его временная сложность для наихудшего и среднего случая составляет O(ⁿ²), а для наилучшего случая - O(n).

Алгоритм Introsort сочетает в себе положительные стороны этих трех алгоритмов. Он начинает с быстрой сортировки, переключается на кучную сортировку, когда глубина рекурсии превышает уровень, основанный на количестве элементов, которые начинают сортироваться, и переключается на сортировку вставками, когда количество элементов меньше некоторого порогового значения.

• Если размер раздела таков, что есть возможность превысить максимальный предел глубины, то Introsort переключается на Heapsort.
• Если размер раздела слишком мал, то Quicksort переключается на сортировку вставками.
• Если размер раздела меньше предела и не слишком мал, то выполняется простая сортировка.

Introsort отличается особенно хорошим поведением во время выполнения. Это один из самых быстрых алгоритмов сравнительной сортировки, используемых сегодня, и является обычной реализацией алгоритма std::sort, поставляемой с библиотеками C++ STL, Microsoft .NET Framework Class Library, GNU Standard C++ library и LLVM libc++ library.

//+------------------------------------------------------------------+
//| Интросорт|
//+------------------------------------------------------------------+
/**
 * Сортировка входного массива на месте с помощью функции сравнения less.
 * Вы можете указать свою собственную функцию сравнения. Если функция не
 * указана, используется сортировка по возрастанию.
 */
template<typename T>
void Introsort(T &arr[]);

//+------------------------------------------------------------------+
//| Интросортируйте, используя указатель на пользовательскую функцию Less().|
//| Пользовательская функция Less() принимает два аргумента и содержит логику |
//| чтобы определить их относительный порядок в отсортированном массиве. Идея заключается в том,|
//| для обеспечения гибкости, чтобы Introsort() можно было использовать для любого |
//| тип (включая типы, определяемые пользователем, такие как объекты или структуры)|
//| и может быть использован для получения любого желаемого порядка сортировки (по возрастанию,|
//| убывающий или пользовательский порядок полей структуры)|.
//+------------------------------------------------------------------+
template<typename T, typename LessFunc>
void Introsort(T &arr[], LessFunc pfnLess);

Функция сравнения Меньше:

bool MyLessFunc(const MyStruct &x, const MyStruct &y)
  {
//--- сортировка по A (по возрастанию)
   if(x.A < y.A) return(true);
   if(x.A > y.A) return(false);

//--- если равны по A, отсортируйте по B (по возрастанию)
   if(x.B < y.B) return(true);
   if(x.B > y.B) return(false);

//--- если равны на B, отсортируйте по C (по возрастанию)
   if(x.C < y.C) return(true);
   if(x.C > y.C) return(false);

//--- все ключи равны
   return(false);
  }


// Определите тип указателя на пользовательскую функцию Less.
typedef bool (*pLess)(const MyStruct &x, const MyStruct &y);


// Сортируем массив структур с помощью пользовательской функции Less.
Introsort(structArray, (pLess)MyLessFunc);