Introsort (Introspective sort) - MetaTrader 5용 라이브러리

Introspective Sort

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(n²).

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(n²) 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.

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.

//+------------------------------------------------------------------+
//| 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:

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);
  }