ハイブリッドアルゴリズム
A hybrid algorithm is an algorithm that combines two or more other algorithms that solve the same problem, either choosing one (depending on the data), or switching between them over the course of the algorithm. This is generally done to combine desired features of each, so that the overall algorithm is better than the individual components.
From Wikipedia, the free encyclopedia
ハイブリッドアルゴリズムとは、同じ問題を解決する2つ以上のアルゴリズムを組み合わせたアルゴリズムで、データに応じてアルゴリズムの1つを選択するか、アルゴリズムの過程で複数のアルゴリズムを切り替えます。それぞれのアルゴリズムの優れた点を組み合わせることで、アルゴリズム全体として個々のアルゴリズムより良いものになります。
異なる問題を解く複数のアルゴリズムを組み合わせるのではなく、同じ問題を解く複数のアルゴリズムを組み合わせます。
ソートのハイブリッドアルゴリズムとして、イントロソートとティムソートを考えます。
イントロソート
イントロソート（英: introsort）は、David Musser（英語版） が1997年に設計したソートアルゴリズムである。最初はクイックソートを行い、再帰のレベルがソートされた要素数（の対数）を超えるとヒープソートに切り替える。最悪でも O(n log n) であり、同時に典型的なデータに対するソートではクイックソートに匹敵する性能を示す。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
最悪時間計算量が\( O (N^2)\)になってしまうクイックソートの欠点を、最悪時間計算量が \( O (N \log N)\) のヒープソートを使って補います。
sort(A : array):
max_depth = 2 * floor(log(length(A)))
introsort(A, depthLimit)
introsort(A, depthLimit):
n = length(A)
# basecase
if n <= 1:
return
if depthLimit == 0:
heapsort(A)
else:
// using quick sort
p = partition(A)
introsort(A[0:p-1], depthLimit - 1)
introsort(A[p+1:n], depthLimit - 1)
ティムソート
Timsort is a hybridstablesorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data.
From Wikipedia, the free encyclopedia
ティムソートとは、マージソートと挿入ソートを組み合わせたハイブリッド安定ソートアルゴリズムで、実世界の多くの種類のデータでうまく動くよう設計されています。
ティムソートは Python の built-in のソートで使われているソートアルゴリズムです。
まず、ティムソートは、配列を 'Run' と呼ばれるブロックに分割します。 挿入ソートでそれぞれの 'Run' ごとにソートを行い、マージソートでマージします。 配列のサイズが規定の 'Run' サイズよりも小さい場合、挿入ソートだけでソートが終了します。
ティムソートはデフォルトの順序を維持する安定ソートなので、オブジェクトのソートに適しています。
