insertion sort – array sorting algorithm – library MetaTrader 5

//+------------------------------------------------------------------+
//|                                                InsertionSort.mq5 |
//|                                    2019-2021, dimitri pecheritsa |
//|                                         mql5.com/en/users/dmipec |
//|------------------------------------------------------------------|
//| cls | insertion sort                                             |
//|------------------------------------------------------------------|
//| use | array sorting algorithm                                    |
//|  best: n; average: n^2; worst: n^2                               |
//|  memory: 1; stable: yes; method: insertion                       |
//|  note: o(n + d), in the worst case over sequences that have d    |
//|inversions.                                                       |
//|------------------------------------------------------------------|
//|  insertion sort is a simple sorting algorithm that builds the    |
//|final sorted array (or list) one item at a time. it is much less  |
//|efficient on large lists than more advanced algorithms such as    |
//|quicksort, heapsort, or merge sort.                               |
//|  when people manually sort cards in a bridge hand, most use a    |
//|method that is similar to insertion sort.                         |
//|  insertion sort provides several advantages:                     |
//|  | simple implementation: jon bentley shows a three-line c       |
//|version, and a five-line optimized version                        |
//|  | efficient for (quite) small data sets, much like other        |
//|quadratic sorting algorithms                                      |
//|  | more efficient in practice than most other simple quadratic   |
//|(i.e., o(n^2)) algorithms such as selection sort or bubble sort   |
//|  | adaptive, i.e., efficient for data sets that are already      |
//|substantially sorted: the time complexity is o(kn) when each      |
//|element in the input is no more than k places away from its sorted|
//|position                                                          |
//|  | stable; i.e., does not change the relative order of elements  |
//|with equal keys                                                   |
//|  | in-place; i.e., only requires a constant amount o(1) of       |
//|additional memory space                                           |
//|  | online; i.e., can sort a list as it receives it               |
//+------------------------------------------------------------------+
//+------------------------------------------------------------------+
//| script   | insertion sort example. sort deals by type            |
//|------------------------------------------------------------------|
//| on start | script program start function                         |
//+------------------------------------------------------------------+
#include <MqhAlgorithmsSortInsertionInsertionSort.mqh>
#include <MqhAlgorithmsSortInsertionFunctions.mqh>
void OnStart(void)
  {
//--- load deals from the terminal for some arbitrary date range in
//the past. these are the items array for the sorter
   ulong deals[];
   DealsLoad(deals,D'2020.12.21',D'2020.12.31');
//--- now create keys array with the deal type values. enumerations
//are integers
   int type[];
   DealsKeyType(deals,type);
//--- sort with insertion sort algorithm
   ArraySort(type,deals,new CInsertionSort<int,ulong>,true);
//--- check the result of sorting by printing a table of symbols
   DealsPrint(deals);
  }
//--------------------------------------------------------------------
//                 deal |        symbol |          type
//--------------------------------------------------------------------
//            169296305 |        BTCUSD | DEAL_TYPE_BUY
//            169300850 |        BTCUSD | DEAL_TYPE_BUY
//            169301072 |        BTCUSD | DEAL_TYPE_BUY
//            169381662 |        BTCUSD | DEAL_TYPE_BUY
//            169400687 |        BTCUSD | DEAL_TYPE_BUY
//            169406060 |        BTCUSD | DEAL_TYPE_BUY
//            169500503 |     .US30Cash | DEAL_TYPE_BUY
//            169500799 |        EURUSD | DEAL_TYPE_BUY
//            169567749 |          TSLA | DEAL_TYPE_BUY
//            169567752 |         BRENT | DEAL_TYPE_BUY
//            169567757 |          TSLA | DEAL_TYPE_BUY
//            169567759 |         BRENT | DEAL_TYPE_BUY
//            169567764 |          TSLA | DEAL_TYPE_BUY
//            169567768 |         BRENT | DEAL_TYPE_BUY
//            169567777 |          TSLA | DEAL_TYPE_BUY
//            169567781 |         BRENT | DEAL_TYPE_BUY
//            169567811 |        EURUSD | DEAL_TYPE_BUY
//            169567820 |        BTCUSD | DEAL_TYPE_BUY
//            169567821 |     .US30Cash | DEAL_TYPE_BUY
//            169567825 |        BTCUSD | DEAL_TYPE_BUY
//            169567826 |     .US30Cash | DEAL_TYPE_BUY
//            169567828 |        BTCUSD | DEAL_TYPE_BUY
//            169567833 |        BTCUSD | DEAL_TYPE_BUY
//            169567837 |        BTCUSD | DEAL_TYPE_BUY
//            169567838 |     .US30Cash | DEAL_TYPE_BUY
//            169567839 |        BTCUSD | DEAL_TYPE_BUY
//            169569207 |     .US30Cash | DEAL_TYPE_BUY
//            169301176 |        BTCUSD | DEAL_TYPE_SELL
//            169519767 |        USDRUB | DEAL_TYPE_SELL
//            169525883 |        USDRUB | DEAL_TYPE_SELL
//            169567751 |        EURUSD | DEAL_TYPE_SELL
//            169567753 |        BTCUSD | DEAL_TYPE_SELL
//            169567755 |     .US30Cash | DEAL_TYPE_SELL
//            169567756 |        USDRUB | DEAL_TYPE_SELL
//            169567758 |        EURUSD | DEAL_TYPE_SELL
//            169567761 |        BTCUSD | DEAL_TYPE_SELL
//            169567762 |     .US30Cash | DEAL_TYPE_SELL
//            169567763 |        USDRUB | DEAL_TYPE_SELL
//            169567765 |        EURUSD | DEAL_TYPE_SELL
//            169567769 |        BTCUSD | DEAL_TYPE_SELL
//            169567771 |     .US30Cash | DEAL_TYPE_SELL
//            169567773 |        USDRUB | DEAL_TYPE_SELL
//            169567778 |        EURUSD | DEAL_TYPE_SELL
//            169567782 |        BTCUSD | DEAL_TYPE_SELL
//            169567788 |     .US30Cash | DEAL_TYPE_SELL
//            169567792 |        USDRUB | DEAL_TYPE_SELL
//            169567808 |          TSLA | DEAL_TYPE_SELL
//            169567817 |         BRENT | DEAL_TYPE_SELL
//            169567824 |          TSLA | DEAL_TYPE_SELL
//            169567841 |        BTCUSD | DEAL_TYPE_SELL
//            169567896 |         BRENT | DEAL_TYPE_SELL
//            169568039 |        USDRUB | DEAL_TYPE_SELL
//--------------------------------------------------------------------