Интросортировка (интроспективная сортировка) с использованием функциональных указателей - библиотека для 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);