| //+------------------------------------------------------------------+
|
| //| 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;
|
| }
|
| //+------------------------------------------------------------------+
|
