関数ポインタを使ったイントロソート（前向きソート - MetaTrader 5のためのライブラリ

イントロソート

これはオリジナルのIntrosortライブラリの 改訂 版で、Introsort()関数は カスタム比較関数へのオプションの関数ポインタを受け付けるようになった。

イントロソートまたはイントロスペクティブソートは、高速な性能を提供するハイブリッドソートアルゴリズムです。これは3つのフェーズに基づく比較ベースのソートアルゴリズムです。イントロソートは、ヒープソートと挿入ソートのアルゴリズムとともに、クイックソートソートを使用します。

クイックソート
クイックソートは分割統治（divide and conquer）アルゴリズムであり、配列中のピボット要素を選択し、他の要素を2つのサブ配列に分割し、要素が大きいか小さいかをチェックする。クイックソートの平均時間はO(nlog(n))、最悪の場合はO(ⁿ 2)である。

ヒープソート
ヒープソートアルゴリズム(Heap sort algoirthm)は、バイナリヒープに基づく比較ベースのソート手法である。不安定なソートアルゴリズムであり、最悪の場合と平均の場合の複雑度はO(nlog(n))、最良の場合の複雑度はO(n)である。

挿入ソート(Insertion Sort)
挿入ソートアルゴリズムは、最終的なソート済み配列を1項目ずつ構築する単純なソート方法である。ワーストケースと平均ケースの時間複雑度はO(ⁿ 2)、ベストケースの時間複雑度はO(n)である。

イントロソートアルゴリズムは、これら3つのアルゴリズムの良いところを組み合わせたものである。クイックソートから始まり、再帰の深さがソート開始要素数に応じたレベルを超えるとヒープソートに切り替わり、要素数がある閾値以下になると挿入ソートに切り替わる。

• パーティションサイズが最大深度制限を超える可能性があるような場合、イントロソートはヒープソートに切り替わる。
• パーティションサイズが小さすぎる場合、クイックソートは挿入ソートに切り替わる。
• パーティションサイズが制限値以下で小さすぎない場合は、単純なクイックソートを実行する。

イントロソートの実行時の動作は特に優れている。これは、現在使用されている比較ソート・アルゴリズムの中で最も高速なものの1つであり、C++ STL、Microsoft .NET Frameworkクラス・ライブラリ、GNU Standard C++ライブラリ、およびLLVM libc++ライブラリで提供されているstd::sortアルゴリズムの通常の実装である。

//+------------------------------------------------------------------+
//| イントロソート|
//+------------------------------------------------------------------+
/**
 * 比較関数 less を使って入力配列をインプレースでソートする。
 * 独自の比較関数を指定することができます。関数が指定されない場合、
 * 昇順ソートが使用されます。
 */
template<typename T>
void Introsort(T &arr[]);

//+------------------------------------------------------------------+
//| カスタムLess()関数へのポインタを使ったイントロソート。
//| カスタム Less() 関数は2つの引数を取り、ロジックを含む。
//| ソートされた配列における相対的な順序を決定する。このアイデアは
//| イントロソート()がどのような｜｜にも使えるように柔軟性を提供する。
//| 型(オブジェクトや構造体のようなユーザー定義型も含む)
//| そして、任意のソート順（昇順、降順）を得るために使用することができる。
//| 構造体フィールドの降順またはカスタムオーダー）。
//+------------------------------------------------------------------+
template<typename T, typename LessFunc>
void Introsort(T &arr[], LessFunc pfnLess);

比較関数 Less：

bool MyLessFunc(const MyStruct &x, const MyStruct &y)
  {
//--- A（昇順）でソート
   if(x.A < y.A) return(true);
   if(x.A > y.A) return(false);

//--- Aで等しい場合、Bでソート（昇順）
   if(x.B < y.B) return(true);
   if(x.B > y.B) return(false);

//--- Bで等しい場合、Cでソート（昇順）
   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);