[ソート] ハイブリッドソート

マージソート マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、というボトムアップの分割統治法による。大きい列を多数の列に分割し、そのそれぞれを...

ハイブリッドアルゴリズム

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 のソートで使われているソートアルゴリズムです。

高速な安定ソートアルゴリズム “TimSort” の解説

ティムソート

まず、ティムソートは、配列を 'Run' と呼ばれるブロックに分割します。 挿入ソートでそれぞれの 'Run' ごとにソートを行い、マージソートでマージします。 配列のサイズが規定の 'Run' サイズよりも小さい場合、挿入ソートだけでソートが終了します。

ティムソートはデフォルトの順序を維持する安定ソートなので、オブジェクトのソートに適しています。

比較ソートと非比較ソート 比較ソートとは、コードに以下のような部分を含む、お互いの要素を比較することによって行われるソートです。 if array < array: swap(array, i, j) 比較ソートは比較によっ...