244 lines
7.9 KiB
MQL5
244 lines
7.9 KiB
MQL5
//+------------------------------------------------------------------+
|
|
//| Introsort.mqh |
|
|
//| Copyright 2000-2025, MetaQuotes Ltd. |
|
|
//| https://www.mql5.com |
|
|
//+------------------------------------------------------------------+
|
|
//+------------------------------------------------------------------+
|
|
//| Struct Introsort<TKey,TItem>. |
|
|
//| Usage: Used by the sort methods for instances of array. |
|
|
//+------------------------------------------------------------------+
|
|
template<typename TKey,typename TItem>
|
|
struct Introsort
|
|
{
|
|
public:
|
|
IComparer<TKey>* comparer;
|
|
TKey keys[];
|
|
TItem items[];
|
|
|
|
Introsort(void) {}
|
|
~Introsort(void) {}
|
|
//--- method for sort array
|
|
void Sort(const int index,const int length);
|
|
private:
|
|
//--- methods for introspective sorting
|
|
void IntroSort(const int lo,const int hi,int depthLimit);
|
|
int PickPivotAndPartition(const int lo,const int hi);
|
|
void InsertionSort(const int lo,const int hi);
|
|
//--- methods for heap sorting
|
|
void Heapsort(const int lo,const int hi);
|
|
void DownHeap(const int i,const int n,const int lo);
|
|
//--- swap methods
|
|
void SwapIfGreaterWithItems(const int a,const int b);
|
|
void Swap(const int i,const int j);
|
|
//--- service methods
|
|
int FloorLog2(int n) const;
|
|
};
|
|
//+------------------------------------------------------------------+
|
|
//| IntrospectiveSort is a hybrid sorting algorithm that provides |
|
|
//| both fast average performance and (asymptotically) optimal |
|
|
//| worst-case performance. It begins with quicksort and switches to |
|
|
//| heapsort when the recursion depth exceeds a level based on the |
|
|
//| number of elements being sorted. |
|
|
//+------------------------------------------------------------------+
|
|
template<typename TKey,typename TItem>
|
|
void Introsort::Sort(const int index,const int length)
|
|
{
|
|
if(length<2)
|
|
return;
|
|
IntroSort(index,length+index-1,2*FloorLog2(ArraySize(keys)));
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| Exchanges the values of a and b, if a greater b. |
|
|
//+------------------------------------------------------------------+
|
|
template<typename TKey,typename TItem>
|
|
void Introsort::SwapIfGreaterWithItems(const int a,const int b)
|
|
{
|
|
if(a!=b)
|
|
{
|
|
if(comparer.Compare(keys[a],keys[b])>0)
|
|
{
|
|
TKey key=keys[a];
|
|
keys[a]=keys[b];
|
|
keys[b]=key;
|
|
if(ArraySize(items)!=NULL)
|
|
{
|
|
TItem item=items[a];
|
|
items[a]=items[b];
|
|
items[b]=item;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| Exchanges the values of a and b. |
|
|
//+------------------------------------------------------------------+
|
|
template<typename TKey,typename TItem>
|
|
void Introsort::Swap(const int i,const int j)
|
|
{
|
|
TKey key=keys[i];
|
|
keys[i]=keys[j];
|
|
keys[j]=key;
|
|
if(ArraySize(items)!=NULL)
|
|
{
|
|
TItem item=items[i];
|
|
items[i]=items[j];
|
|
items[j]=item;
|
|
}
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| Returns the closest integer value less than or equal to the base |
|
|
//| 2 log of the input value. |
|
|
//+------------------------------------------------------------------+
|
|
template<typename TKey,typename TItem>
|
|
int Introsort::FloorLog2(int n) const
|
|
{
|
|
int result=0;
|
|
while(n>=1)
|
|
{
|
|
result++;
|
|
n=n/2;
|
|
}
|
|
return(result);
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| Introspective sort. |
|
|
//+------------------------------------------------------------------+
|
|
template<typename TKey,typename TItem>
|
|
void Introsort::IntroSort(const int lo,int hi,int depthLimit)
|
|
{
|
|
const int IntrosortSizeThreshold=16;
|
|
while(hi>lo)
|
|
{
|
|
int partitionSize = hi - lo + 1;
|
|
if(partitionSize <= IntrosortSizeThreshold)
|
|
{
|
|
if(partitionSize==1)
|
|
{
|
|
return;
|
|
}
|
|
if(partitionSize==2)
|
|
{
|
|
SwapIfGreaterWithItems(lo,hi);
|
|
return;
|
|
}
|
|
if(partitionSize==3)
|
|
{
|
|
SwapIfGreaterWithItems(lo,hi-1);
|
|
SwapIfGreaterWithItems(lo,hi);
|
|
SwapIfGreaterWithItems(hi-1,hi);
|
|
return;
|
|
}
|
|
InsertionSort(lo,hi);
|
|
return;
|
|
}
|
|
if(depthLimit==0)
|
|
{
|
|
Heapsort(lo,hi);
|
|
return;
|
|
}
|
|
depthLimit--;
|
|
int p=PickPivotAndPartition(lo,hi);
|
|
IntroSort(p+1,hi,depthLimit);
|
|
hi=p-1;
|
|
}
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| Insertion sort. |
|
|
//+------------------------------------------------------------------+
|
|
template<typename TKey,typename TItem>
|
|
void Introsort::InsertionSort(const int lo,const int hi)
|
|
{
|
|
int i,j;
|
|
TKey t;
|
|
TItem dt;
|
|
for(i=lo; i<hi; i++)
|
|
{
|
|
j = i;
|
|
t = keys[i + 1];
|
|
dt=(ArraySize(items)!=NULL) ? (TItem)items[i+1] : (TItem)NULL;
|
|
while(j>=lo && comparer.Compare(t,keys[j])<0)
|
|
{
|
|
keys[j+1]=keys[j];
|
|
if(ArraySize(items)!=NULL)
|
|
{
|
|
items[j+1]=items[j];
|
|
}
|
|
j--;
|
|
}
|
|
keys[j+1]=t;
|
|
if(ArraySize(items)!=NULL)
|
|
{
|
|
items[j+1]=dt;
|
|
}
|
|
}
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| Array partitioning by a quick sort algorithm. |
|
|
//+------------------------------------------------------------------+
|
|
template<typename TKey,typename TItem>
|
|
int Introsort::PickPivotAndPartition(const int lo,const int hi)
|
|
{
|
|
//--- Compute median-of-three. But also partition them, since we've done the comparison.
|
|
int mid=lo+(hi-lo)/2;
|
|
SwapIfGreaterWithItems(lo,mid);
|
|
SwapIfGreaterWithItems(lo,hi);
|
|
SwapIfGreaterWithItems(mid,hi);
|
|
TKey pivot=keys[mid];
|
|
Swap(mid,hi-1);
|
|
int left=lo,right=hi-1;
|
|
while(left<right)
|
|
{
|
|
while(comparer.Compare(keys[++left], pivot) < 0);
|
|
while(comparer.Compare(pivot, keys[--right]) < 0);
|
|
if(left>=right)
|
|
break;
|
|
Swap(left,right);
|
|
}
|
|
//--- Put pivot in the right location.
|
|
Swap(left,(hi-1));
|
|
return (left);
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| Heap sorting algorithm. |
|
|
//+------------------------------------------------------------------+
|
|
template<typename TKey,typename TItem>
|
|
void Introsort::Heapsort(const int lo,const int hi)
|
|
{
|
|
int n=hi-lo+1;
|
|
for(int i=n/2; i>=1; i=i-1)
|
|
{
|
|
DownHeap(i,n,lo);
|
|
}
|
|
for(int i=n; i>1; i=i-1)
|
|
{
|
|
Swap(lo,lo+i-1);
|
|
DownHeap(1,i-1,lo);
|
|
}
|
|
}
|
|
//+------------------------------------------------------------------+
|
|
//| Downheap function for heapsort. |
|
|
//+------------------------------------------------------------------+
|
|
template<typename TKey,typename TItem>
|
|
void Introsort::DownHeap(int i,const int n,const int lo)
|
|
{
|
|
bool f=ArraySize(items)!=0;
|
|
TKey d=keys[lo+i-1];
|
|
TItem dt=f ? (TItem)items[lo+i-1] : (TItem)NULL;
|
|
|
|
while(i<=n/2)
|
|
{
|
|
int child=2*i;
|
|
if(child<n && comparer.Compare(keys[lo+child-1],keys[lo+child])<0)
|
|
child++;
|
|
if(!(comparer.Compare(d,keys[lo+child-1])<0))
|
|
break;
|
|
keys[lo+i-1]=keys[lo+child-1];
|
|
if(f)
|
|
items[lo+i-1]=items[lo+child-1];
|
|
i=child;
|
|
}
|
|
keys[lo+i-1]=d;
|
|
if(f)
|
|
items[lo+i-1]=dt;
|
|
}
|
|
//+------------------------------------------------------------------+
|