Introsort using function pointers - MetaTrader 5 Library - MT4/MT5 Resources

introspective sort

This is a modified version of the original Introsort library , now the Introsort() function accepts an optional function pointer to a custom comparison function.

Introductory or introspective sort is a hybrid sorting algorithm that provides fast performance. It is a comparison-based sorting algorithm based on three phases. It uses quick sort as well as heap sort and insertion sort algorithms.

Quick Sort <br/>Quick sort is a divide-and-conquer algorithm that works by selecting a pivot in the array, then dividing the other elements into two sub-arrays, checking whether the elements are greater or less than. On average, the quick sort algorithm takes O(nlog(n)) time, and the worst-case complexity is O(n ² ).

Heap sort <br/>The heap sort algorithm is a comparison sorting method based on binary heaps. It is an unstable sorting algorithm. The worst-case and average-case time complexity is O(nlog(n)), and the best-case time complexity is O(n).

Insertion Sort <br/>The insertion sort algorithm is a simple sorting method that builds the final sorted array in one go. The worst-case and average-case time complexity is O(n ² ), and the best-case is O(n).

The Introsort algorithm combines the advantages of these three algorithms. It starts with quick sort, switches to heap sort when the recursion depth exceeds a level based on the number of elements to start sorting, and switches to insertion sort when the number of elements is less than a certain threshold.

Introsort has particularly good runtime behavior. It is one of the fastest comparison sorting algorithms in use today, and is the common implementation of the std::sort algorithm provided by the C++ STL, the Microsoft .NET Framework class library, the GNU Standard C++ Library, and the LLVM libc++ library.

http://en.wikipedia.org/wiki/Introsort

https://iq.opengenus.org/intro-sort/

 //+------------------------------------------------------------------+
//|Introduction |
//+------------------------------------------------------------------+
/**
 * Use the less comparison function to sort the input array in place.
 * You can specify your own comparison function. If no function * is specified, ascending sorting is used.
 */
Template < type name > blank Introsort(T &arr[]); //+----------------------------------------------------------------------------------+
//|Use a pointer to a custom Less() function for Introsort.            |
//|Custom Less() function takes two parameters and contains logic|
//|Determine their relative order in the sorted array. The idea is |
//|Provides flexibility so that Introsort() can be used with any |
//|Types (including user-defined types such as objects or structures)
//| and can be used to get any desired sort order (ascending, |
//|Descending or custom order of structure fields).                |
//+------------------------------------------------------------------+
Template < type name tons, type name less function> blank Introsort(T &arr[], LessFunc pfnLess);

Fewer comparison functions:

You can specify your own comparison function. If no function is specified, ascending sorting is used. The custom Less() function takes two arguments and contains logic that determines their relative order in the sorted array. The idea is to provide flexibility so that Introsort() can be used for any type (including user-defined types) and can be used to get any desired order (increasing, descending, or any other). For example, to sort an array of objects or structures (user-defined types) in a custom sort order:

boolean myLessFunc( const mystruct&x, const mystruct&y)
  { //--- Sort by A (asc) if (xA < yA) return ( true );
if (xA > yA) return ( false ); //--- if A is equal, sort by B (asc) if (xB < yB) return ( true );
if (xB > yB) return ( false ); //--- if B are equal, sort by C (asc) if (xC < yC) return ( true );
return ( false ) if (xC > yC); //--- return ( false ) if all keys are equal ;
  } // Define the pointer type of the custom Less function.
Type definition Boolean (*pLess)( const my structure&x, const my structure&y); // Use custom Less function to sort the structure array. Introsort(structArray, (pLess)MyLessFunc);