함수 포인터를 사용한 인트로소트(내성적 정렬) - MetaTrader 5용 라이브러리

내성적 정렬

이것은 원래 Introsort 라이브러리의 개정된 버전으로, 이제Introsort() 함수는 사용자 정의 비교 함수에 대한 선택적 함수 포인터를 허용합니다.

인트로 또는 내성적 정렬은 빠른 성능을 제공하는 하이브리드 정렬 알고리즘입니다. 3단계에 기반한 비교 기반 정렬 알고리즘입니다. 힙 정렬 및 삽입 정렬 알고리즘과 함께 빠른 정렬 정렬을 사용합니다.

빠른 정렬
빠른 정렬은 배열에서 피벗 요소를 선택한 다음 다른 요소를 두 개의 하위 배열로 분할하여 요소가 더 크거나 작은지 조건을 확인하는 분할 및 정복 알고리즘입니다. 평균적으로 빠른 정렬 알고리즘은 O(nlog(n)) 시간이 걸리며, 최악의 경우 복잡도는 O(ⁿ²)입니다.

힙 정렬
힙 정렬 알고리즘은 이진 힙 기반의 비교 기반 정렬 방법입니다. 최악의 경우와 평균적인 경우의 시간 복잡도는 O(nlog(n)), 최상의 경우의 시간 복잡도는 O(n)인 불안정한 정렬 알고리즘입니다.

삽입 정렬
삽입 정렬 알고리즘은 한 번에 한 항목씩 최종 정렬된 배열을 만드는 간단한 정렬 방법입니다. 최악의 경우와 평균적인 경우의 시간 복잡도는 O(ⁿ²), 최상의 경우의 시간 복잡도는 O(n)입니다.

인트로소트 알고리즘은 이 세 가지 알고리즘의 좋은 부분을 결합한 것입니다. 빠른 정렬로 시작하여 정렬을 시작한 요소 수에 따라 재귀 깊이가 일정 수준을 초과하면 힙소트로 전환하고, 요소 수가 임계값보다 작으면 삽입 정렬로 전환합니다.

• 파티션 크기가 최대 깊이 제한을 초과할 가능성이 있는 경우 인트로소트는 힙소트로 전환됩니다.
• 파티션 크기가 너무 작으면 퀵소트가 삽입 정렬로 전환됩니다.
• 파티션 크기가 한도 이하이고 너무 작지 않은 경우 간단한 빠른 정렬을 수행합니다.

인트로소트는 특히 런타임 동작이 우수합니다. 이것은 현재 사용되는 가장 빠른 비교 정렬 알고리즘 중 하나이며, C++ STL, Microsoft .NET Framework 클래스 라이브러리, GNU 표준 C++ 라이브러리 및 LLVM libc++ 라이브러리와 함께 제공되는 std::sort 알고리즘의 일반적인 구현입니다.

//+------------------------------------------------------------------+
//| 인트로|
//+------------------------------------------------------------------+
/**
 * 비교 함수를 적게 사용하여 입력 배열을 제자리에서 정렬합니다.
 * 직접 비교 함수를 지정할 수 있습니다. 
 * 함수를 지정하지 않으면 오름차순 정렬이 사용됩니다.
 */
template<typename T>
void Introsort(T &arr[]);

//+------------------------------------------------------------------+
//| 사용자 지정 Less() 함수에 대한 포인터를 사용하여 인트로 정렬합니다.
//| 사용자 지정 Less() 함수는 두 개의 인수를 받고 로직을 포함합니다.
//|를 사용하여 정렬된 배열에서 상대적인 순서를 결정합니다. 아이디어는 |
//|를 추가하여 유연성을 제공함으로써 모든 |
//| 유형(객체 또는 구조체와 같은 사용자 정의 유형 포함) |
//|를 사용하여 원하는 정렬 순서(오름차순, ||)를 얻을 수 있습니다.
//| 구조 필드의 내림차순 또는 사용자 지정 순서).
//+------------------------------------------------------------------+
template<typename T, typename LessFunc>
void Introsort(T &arr[], LessFunc pfnLess);

비교 함수 Less:

bool MyLessFunc(const MyStruct &x, const MyStruct &y)
  {
//--- 정렬 기준 A(asc)
   if(x.A < y.A) return(true);
   if(x.A > y.A) return(false);

//--- A에서 같으면 B(asc)로 정렬합니다.
   if(x.B < y.B) return(true);
   if(x.B > y.B) return(false);

//--- B에서 같으면 C(asc)를 기준으로 정렬합니다.
   if(x.C < y.C) return(true);
   if(x.C > y.C) return(false);

//--- 모든 키는 동일합니다.
   return(false);
  }


// 사용자 지정 Less 함수에 대한 포인터 유형을 정의합니다.
typedef bool (*pLess)(const MyStruct &x, const MyStruct &y);


// 사용자 정의 Less 함수를 사용하여 구조 배열을 정렬합니다.
Introsort(structArray, (pLess)MyLessFunc);