C++で実装するティムソート（Timsort）アルゴリズム：仕組みとコード例

ティムソート（Timsort）は、マージソートと挿入ソートの考え方を組み合わせた安定なソートアルゴリズムです。両者を融合させたハイブリッド型アルゴリズムとも呼ばれ、JavaやPython、C、C++など多くの言語の標準ソート機能に採用されています。基本的な発想は、まず小さな塊をそれぞれ挿入ソートで整列し、その後マージソートのマージ処理を使って塊同士を統合していくというものです。

動作原理

ティムソートでは、配列を小さな塊に分割します。この塊は「RUN」と呼ばれます。各RUNは挿入ソートの手法で整列され、すべてのRUNが整列し終えた後、マージ関数によって順次統合されていきます。

配列のサイズがRUNよりも小さい場合もあります。そのような場合は、配列全体が挿入ソートによって直接整列されます。通常、RUNのサイズは32〜64程度で、配列の規模に応じて調整されます。また、マージ処理はサブ配列のサイズが2のべき乗である場合にのみ実行されます。

挿入ソートを採用するメリットは、小さなサイズの配列に対して高い効率を発揮できる点にあります。

計算量：

• 最良ケース − Ω(n)

• 平均ケース − O(n log n)

• 最悪ケース − O(n log n)

ティムソートのアルゴリズム手順

• サイズ32のRUNを初期化します。

• RUNサイズごとの塊に対して挿入ソートを実装します。

• 関数 merge(int arr[], int l, int m, int r) は、配列・左側の要素・配列の中央位置・右側の要素を引数として受け取ります。この関数は、サイズ32の整列済みの塊をマージした結果を返します。

• 左側の要素をすべて格納する配列の長さと、右側の要素をすべて格納する配列の長さを初期化します。

• 左配列と右配列への格納が完了したら、両方の配列を反復処理します。

• 左配列の要素が右配列の要素以下の場合、その要素をマージ先の配列に格納します。

• そうでない場合は、右配列の要素をマージ先の配列に格納します。

• 左配列および右配列に残った要素を、マージ先の配列にコピーします。

• 関数 timSortAlgo(int arr[], int n) は、配列とそのサイズを引数として受け取ります。最初に挿入ソートを呼び出し、その後で配列要素のマージを行います。

• ティムソートによる最終的な整列結果を配列として返します。

C++実装例

#include<bits/stdc++.h>
using namespace std;
const int RUN = 32; // 塊（チャンク）を作るためのRUNの初期化

// RUNサイズの塊に対して挿入ソートを実装
void insertionSort(int arr[], int left, int right){
    for (int i = left + 1; i <= right; i++){
        int t = arr[i];
        int j = i - 1;
        while (j >= left && t < arr[j]){
            arr[j+1] = arr[j--];
        }
        arr[j+1] = t;
    }
}

// マージ関数により、サイズ32の整列済みの塊を1つに統合
void merge(int arr[], int l, int m, int r){
    int len1 = m - l + 1, len2 = r - m;
    int left[len1], right[len2];
    for (int i = 0; i < len1; i++)
        left[i] = arr[l + i]; // 左配列への格納
    for (int i = 0; i < len2; i++)
        right[i] = arr[m + 1 + i]; // 右配列への格納
    int i = 0;
    int j = 0;
    int k = l;
    while (i < len1 && j < len2){ // 左右両方の配列を反復処理
        if (left[i] <= right[j]){ // 左の要素が小さい場合、iを進めながらマージ先へ格納
            arr[k] = left[i];
            i++;
        } else {
            arr[k] = right[j]; // 右配列の要素の方が大きい場合、jを進める
            j++;
        }
        k++;
    }
    while (i < len1){ // 左配列に残った要素をコピー
        arr[k] = left[i];
        k++;
        i++;
    }
    while (j < len2){ // 右配列に残った要素をコピー
        arr[k] = right[j];
        k++;
        j++;
    }
}

void timSortAlgo(int arr[], int n){
    // insertionSort() を呼び出す
    for (int i = 0; i < n; i += RUN) insertionSort(arr, i, min((i+31), (n-1)));
    // サイズRUN（または32）からマージを開始し、2*RUNまで続ける
    for (int s = RUN; s < n; s = 2*s){
        // 左部分配列の開始点を選択
        // arr[left..left+size-1] と arr[left+size, left+2*size-1] をマージする
        // マージのたびに left を 2*size ずつ増加させる
        for (int left = 0; left < n; left += 2*s){
            int mid = left + s - 1; // 左部分配列の終了点を求める（mid+1は右部分配列の開始点）
            int right = min((left + 2*s - 1), (n-1));
            merge(arr, left, mid, right); // 部分配列 arr[left.....mid] と arr[mid+1....right] をマージ
        }
    }
}

void printArray(int arr[], int n){
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

// ティムソートアルゴリズムを実装するメイン関数
int main(){
    int arr[] = {-2, 7, 15, -14, 0, 15, 0, 7, -7, -4, -13, 5, 8, -14, 12};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "元の配列： ";
    printArray(arr, n);
    // 配列をソートするためにtimSortAlgo関数を呼び出す
    timSortAlgo(arr, n);
    cout << "ティムソートによるソート後の配列： ";
    printArray(arr, n); // 出力関数の呼び出し
    return 0;
}

実行結果

元の配列： -2 7 15 -14 0 15 0 7 -7 -4 -13 5 8 -14 12 
ティムソートによるソート後の配列： -14 -14 -13 -7 -4 -2 0 0 5 7 7 8 12 15 15