Introsort (Introspective sort) - library for MetaTrader 5

Introsort (Introspective sort) – library MetaTrader 5

by

Introspective Sort

Intro or Introspective sort is a hybrid sorting algorithm that provide fast performance. It is a comparison based sorting algorithm based on three phases. It uses the quicksort sort along with heapsort and insertion-sort algorithms. 

Quick Sort
Quick sort is a divide and conquer algorithm which works by selecting a pivot element in the array, then partitions the other elements into two subarrays checking the condition whether the elements are greater or smaller. On average the quick sort alogirthm takes O(nlog(n)) time, with worst case complexity of O(n2).

Heap Sort
Heap sort algoirthm is a binary-heap based comparison based sorting method. It is an unstable sorting algorithm with worst case and average case time complexity of O(nlog(n)), and best case time complexity of O(n).

Insertion Sort
Insertion sort algorithm is a simple sorting method that builds the final sorted array one item at a time. It’s time complexity for worst case and average case is O(n2) and best case is O(n).

Introsort algorithm combines the good parts of these three algorithms. It begins with quick sort, switching to heapsort when the recursion depth exceeds a level based on the number of elements begin sorted and switchs to insertion sort when the number of elements are less than some threshold value.

  • If the partition size is such that there is a possibility to exceed the maximum depth limit then the Introsort switches to Heapsort.
  • If the partition size is too small then Quicksort switches to Insertion Sort.
  • If the partition size is under the limit and not too small, then it performs a simple quicksort.
Alternative:  Cauchy derivative YTG - indicator MetaTrader 5

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

References:

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

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

Code:

//+------------------------------------------------------------------+
//| Introsort                                                        |
//+------------------------------------------------------------------+
/**
 * Sort the input array in-place using comparison function less.
 * You can specify your own comparison function. If no function is
 * specified, ascending sort is used.
 */
template<typename T>
void Introsort(T &arr[]);

    Comparison function Less:

    You can specify your own comparison function. If no function is specified, ascending sort is used. A custom Less() function takes two arguments and contains logic to decide 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 obtain any desired order (increasing, decreasing or any other). For example, to sort an array of objects or structures (user defined types) in a custom sort order:

    bool Less(const CRecord& left, const CRecord& right)
  {
   // sort on key a in descending order
   if(left.a > right.a) return(true);
   if(left.a < right.a) return(false);

   // if two objects are equal on key a, 
   // sort on key b in ascending order
   if(left.b < right.b) return(true);
   if(left.b > right.b) return(false);

   ...
   ...

//--- all keys are equal
   return(false);
  }

    Introsort (Introspective sort) – library MetaTrader 5
    📈 ROBOTFX MetaTrader Expert Advisors and Indicators to maximize profits and minimize the risks
    Alternative:  FineTuningMACandle_Chl_HTF - indicator MetaTrader 5

    Similar MetaTrader Trading Tools:

    • Radix sort (The fastest numeric sort) - library for MetaTrader 5
      Radix sort (The fastest numeric sort) - library MetaTrader 5       RadixSort Algorithm RadixSort sorts numeric data (integers or float) by considering a string of numbers where digit by digit sort…
    • introsort - array sorting algorithm - library for MetaTrader 5
      introsort - array sorting algorithm - library MetaTrader 5       //+------------------------------------------------------------------+ //|                                                    Introsort.mq5 | //|                                    2019-2021, dimitri pecheritsa | //|                                         mql5.com/en/users/dmipec | //|------------------------------------------------------------------| //|   c| array sorting algorithm                                     | //|  introsort or introspective…
    • gnome sort - array sorting algorithm - library for MetaTrader 5
      gnome sort - array sorting algorithm - library MetaTrader 5       //+------------------------------------------------------------------+ //|                                                    GnomeSort.mq5 | //|                                    2019-2021, dimitri pecheritsa | //|                                         mql5.com/en/users/dmipec | //|------------------------------------------------------------------| //|  c  | gnome sort                                                 | //|------------------------------------------------------------------| //| use | array…
    • insertion sort - array sorting algorithm - library for MetaTrader 5
      insertion sort - array sorting algorithm - library…       //+------------------------------------------------------------------+ //|                                                InsertionSort.mq5 | //|                                    2019-2021, dimitri pecheritsa | //|                                         mql5.com/en/users/dmipec | //|------------------------------------------------------------------| //| cls | insertion sort                                             | //|------------------------------------------------------------------| //| use…
    • selection sort - array sorting algorithm - library for MetaTrader 5
      selection sort - array sorting algorithm - library…       //+------------------------------------------------------------------+ //|                                                SelectionSort.mq5 | //|                                    2019-2021, dimitri pecheritsa | //|                                         mql5.com/en/users/dmipec | //+------------------------------------------------------------------+ //| selection sort - array sorting algorithm                         | //+------------------------------------------------------------------+…
    • shell sort - array sorting algorithm - library for MetaTrader 5
      shell sort - array sorting algorithm - library MetaTrader 5       //+------------------------------------------------------------------+ //|                                                    ShellSort.mq5 | //|                                    2019-2021, dimitri pecheritsa | //|                                         mql5.com/en/users/dmipec | //+------------------------------------------------------------------+ //+------------------------------------------------------------------+ //| shell sort - array sorting algorithm                             |…
    • heap sort - array sorting algorithm - library for MetaTrader 5
      heap sort - array sorting algorithm - library MetaTrader 5       //+------------------------------------------------------------------+ //|                                                     HeapSort.mq5 | //|                                  2019 - 2021, dimitri pecheritsa | //|                             https://www.mql5.com/en/users/dmipec | //+------------------------------------------------------------------+ //+------------------------------------------------------------------+ //| heap sort - array…
    • merge sort - a merging method comparison-based sorting algorithm - library for MetaTrader 5
      merge sort - a merging method comparison-based…       //+------------------------------------------------------------------+ //|                                                    MergeSort.mq5 | //|                                    2019-2020, dimitri pecheritsa | //|                                                 792112@gmail.com | //+------------------------------------------------------------------+ //   merge sort - a merging method comparison-based sorting…