226 lines
17 KiB
MQL5
226 lines
17 KiB
MQL5
//+------------------------------------------------------------------+
|
|
//| Introsort.mqh |
|
|
//| Copyright © 2018, Amr Ali |
|
|
//| https://www.mql5.com/en/users/amrali |
|
|
//+------------------------------------------------------------------+
|
|
|
|
//+------------------------------------------------------------------+
|
|
//| 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.
|
|
*
|
|
* Generally, the fastest comparison-based sort algorithm for arrays.
|
|
* (esp. if large size).
|
|
* Average time complexity: O(n log n)
|
|
* Worst-case time complexity: O(n log n)
|
|
* Stable : no
|
|
*
|
|
* Introsort is a hybrid sorting algorithm that uses three sorting algorithm
|
|
* to minimise the running time: Quicksort, Heapsort and Insertion Sort.
|
|
* Introsort begins with quicksort and if the recursion depth goes more
|
|
* than a particular limit it switches to Heapsort to avoid Quicksort’s
|
|
* worst case O(N2) time complexity. It also uses insertion sort when the
|
|
* number of elements to sort is quite less.
|
|
*/
|
|
template<typename T>
|
|
void Introsort(T &arr[])
|
|
{
|
|
//--- use default Less function
|
|
typedef bool (*LessFunc)(const T, const T);
|
|
Introsort(arr, (LessFunc)IntrosortInternal::Less<T>);
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| Introsort using a pointer to custom Less() function. |
|
|
//| 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 like objects or structures) |
|
|
//| and can be used to obtain any desired sort order (ascending, |
|
|
//| descending or custom order of structure fields). |
|
|
//+------------------------------------------------------------------+
|
|
template<typename T, typename LessFunc>
|
|
void Introsort(T &arr[], LessFunc pfnLess)
|
|
{
|
|
IntrosortInternal::IntrosortUtil(arr, 0, ArraySize(arr) - 1, pfnLess);
|
|
}
|
|
|
|
namespace IntrosortInternal
|
|
{
|
|
//+------------------------------------------------------------------+
|
|
//| |
|
|
//+------------------------------------------------------------------+
|
|
template<typename T, typename LessFunc>
|
|
void IntrosortUtil(T &arr[], int lo, int hi, LessFunc pfnLess)
|
|
{
|
|
int size = hi - lo + 1;
|
|
int depthLimit = 2 * (int)MathFloor(MathLog(size)/M_LN2);
|
|
IntrosortUtil(arr, lo, hi, depthLimit, pfnLess);
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| |
|
|
//+------------------------------------------------------------------+
|
|
/**
|
|
* depthLimit:
|
|
* It represents maximum depth for recursion. It is typically chosen
|
|
* as log of length of input array. The idea is to ensure that the worst
|
|
* case time complexity remains O(N log N).
|
|
*/
|
|
template<typename T, typename LessFunc>
|
|
void IntrosortUtil(T &arr[], int lo, int hi, int depthLimit, LessFunc pfnLess)
|
|
{
|
|
const int InsertsortSizeThreshold = 16;
|
|
while(lo < hi)
|
|
{
|
|
int partitionSize = hi - lo + 1;
|
|
//--- Insertion sort is faster for small partitions.
|
|
if(partitionSize <= InsertsortSizeThreshold)
|
|
{
|
|
InsertionSort(arr, lo, hi, pfnLess);
|
|
return;
|
|
}
|
|
//--- If recursion depth exceeds limit, switch to heapsort to guarantee O(n log n).
|
|
if(--depthLimit == 0)
|
|
{
|
|
HeapSort(arr, lo, hi, pfnLess);
|
|
return;
|
|
}
|
|
|
|
//--- Pick pivot as the median-of-three.
|
|
T pivot = Median3(arr, lo, hi, pfnLess);
|
|
|
|
//--- Hoare’s partitioning scheme.
|
|
int p = partition(arr, lo, hi, pivot, pfnLess);
|
|
|
|
//--- Sort the left partition first using recursion and do tail recursion elimination for
|
|
//--- the right-hand partition.
|
|
IntrosortUtil(arr, lo, p - 1, depthLimit, pfnLess);
|
|
lo = p;
|
|
}
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| partition subarray a[lo..hi] around pivot and return pivot index.|
|
|
//+------------------------------------------------------------------+
|
|
template<typename T, typename LessFunc>
|
|
int partition(T &arr[], int lo, int hi, T& pivot, LessFunc pfnLess)
|
|
{
|
|
while(lo <= hi)
|
|
{
|
|
while(pfnLess(arr[lo], pivot)) lo++;
|
|
while(pfnLess(pivot, arr[hi])) hi--;
|
|
if(lo > hi)
|
|
break;
|
|
Swap(arr[lo++], arr[hi--]);
|
|
}
|
|
return lo;
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| Insertion Sort |
|
|
//+------------------------------------------------------------------+
|
|
template<typename T, typename LessFunc>
|
|
void InsertionSort(T &arr[], int lo, int hi, LessFunc pfnLess)
|
|
{
|
|
for(int i = lo + 1; i <= hi; i++)
|
|
{
|
|
if(pfnLess(arr[i], arr[i - 1]))
|
|
{
|
|
T curr = arr[i];
|
|
arr[i] = arr[i - 1];
|
|
int j = i;
|
|
while(--j > lo && pfnLess(curr, arr[j - 1]))
|
|
arr[j] = arr[j - 1];
|
|
arr[j] = curr;
|
|
}
|
|
}
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| Heap Sort |
|
|
//+------------------------------------------------------------------+
|
|
template<typename T, typename LessFunc>
|
|
void HeapSort(T &arr[], int lo, int hi, LessFunc pfnLess)
|
|
{
|
|
int size = hi - lo + 1;
|
|
for(int i = size / 2 - 1; i >= 0; i--)
|
|
{
|
|
Heapify(arr, i, size, lo, pfnLess);
|
|
}
|
|
for(int i = size - 1; i > 0; i--)
|
|
{
|
|
Swap(arr[lo], arr[lo + i]);
|
|
Heapify(arr, 0, i, lo, pfnLess);
|
|
}
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| Rebuilds the heap. |
|
|
//+------------------------------------------------------------------+
|
|
template<typename T, typename LessFunc>
|
|
void Heapify(T &arr[], int parent, int heap_size, int lo, LessFunc pfnLess)
|
|
{
|
|
T temp = arr[lo + parent];
|
|
int child = parent * 2 + 1;
|
|
while(child < heap_size)
|
|
{
|
|
if(child + 1 < heap_size && pfnLess(arr[lo + child], arr[lo + child + 1]))
|
|
{
|
|
child++;
|
|
}
|
|
if(!pfnLess(temp, arr[lo + child]))
|
|
{
|
|
break;
|
|
}
|
|
arr[lo + parent] = arr[lo + child];
|
|
parent = child;
|
|
child = parent * 2 + 1;
|
|
}
|
|
arr[lo + parent] = temp;
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| Get the median of three array elements. |
|
|
//+------------------------------------------------------------------+
|
|
template<typename T, typename LessFunc>
|
|
T Median3(T &arr[], int lo, int hi, LessFunc pfnLess)
|
|
{
|
|
int mid = lo + (hi - lo) / 2;
|
|
Sort3(arr, lo, mid, hi, pfnLess);
|
|
return arr[mid];
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| Sorts the elements a, b and c using comparison function less. |
|
|
//+------------------------------------------------------------------+
|
|
template<typename T, typename LessFunc>
|
|
void Sort3(T &xs[], int a, int b, int c, LessFunc pfnLess)
|
|
{
|
|
Sort2(xs, a, b, pfnLess);
|
|
Sort2(xs, b, c, pfnLess);
|
|
Sort2(xs, a, b, pfnLess);
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| Sorts the elements a and b using comparison function less. |
|
|
//+------------------------------------------------------------------+
|
|
template<typename T, typename LessFunc>
|
|
void Sort2(T &xs[], int a, int b, LessFunc pfnLess)
|
|
{
|
|
if(pfnLess(xs[b], xs[a]))
|
|
Swap(xs[a], xs[b]);
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| Swaps two array elements using references. |
|
|
//+------------------------------------------------------------------+
|
|
template<typename T>
|
|
void Swap(T& a, T& b)
|
|
{
|
|
T temp = a;
|
|
a = b;
|
|
b = temp;
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| Generic comparison function Less (ascending). |
|
|
//+------------------------------------------------------------------+
|
|
template<typename T>
|
|
bool Less(const T left,const T right)
|
|
{ return left < right; }
|
|
|
|
}
|
|
//+------------------------------------------------------------------+
|