C++でのティムソートアルゴリズム

ティムソートは、マージソートと挿入ソートの概念を使用する安定したソートアルゴリズムです。挿入とマージソートのハイブリッドアルゴリズムと呼ぶこともできます。これは、Java、Python、C、およびC++の組み込みのソートアルゴリズムで広く使用されています。このアルゴリズムの背後にある考え方は、挿入ソートを使用して小さなチャンクをソートし、次にマージソートアルゴリズムのマージ機能を使用してすべての大きなチャンクをマージすることです。

作業中

このアルゴリズムでは、配列は小さなチャンクに分割されます。チャンクはRUNとして知られています。各RUNは、挿入ソート手法を使用して取得およびソートされます。すべてのRUNがソートされた後、これらはマージ機能を使用してマージされます。

配列のサイズがRUNより小さくなる場合があります。このような場合、配列は挿入ソート手法によってソートされます。通常、RUNチャンクは配列のサイズに応じて32から64まで変化します。マージ関数は、サブアレイチャンクのサイズが2の累乗である場合にのみマージされます。

挿入ソートを使用する利点は、サイズが小さい配列では挿入ソートが正常に機能するためです。

時間計算量 −

• ベストケース-オメガ（n）

• 平均的なケース-O（nlogn）

• 最悪の場合-O（nlogn）

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

• 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; // Initialising the RUN to get chunks
void insertionSort(int arr[], int left, int right) // Implementing insertion
sort for RUN size chunks{
   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;
   }
}
void merge(int arr[], int l, int m, int r) // using the merge function the
sorted chunks of size 32 are merged into one{
   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]; // Filling left array
   for (int i = 0; i < len2; i++)
      right[i] = arr[m + 1 + i]; // Filling right array
   int i = 0;
   int j = 0;
   int k = l;
   while (i < len1 && j < len2) // Iterate into both arrays left and right{
      if (left[i] <= right[j]) // IF element in left is less then increment i by pushing into larger array{
         arr[k] = left[i];
         i++;
      } else {
         arr[k] = right[j]; // Element in right array is greater
         increment j
         j++;
      }
      k++;
   }
   while (i < len1) // This loop copies remaining element in left array{
      arr[k] = left[i];
      k++;
      i++;
   }
   while (j < len2) // This loop copies remaining element in right array{
      arr[k] = right[j];
      k++;
      j++;
   }
}
void timSortAlgo(int arr[], int n){
   for (int i = 0; i < n; i+=RUN) insertionSort(arr, i, min((i+31), (n-1))); //Call insertionSort()
   for (int s = RUN; s < n; s = 2*s) // Start merging from size RUN (or 32). It will continue upto 2*RUN{
      // pick starting point of left sub array. We are going to merge
      arr[left..left+size-1]
      // and arr[left+size, left+2*size-1]
      // After every merge, we
      // increase left by 2*size
      for (int left = 0; left < n;left += 2*s){
         int mid = left + s - 1; // find ending point of left sub
         array mid+1 is starting point of right sub array
         int right = min((left + 2*s - 1), (n-1));
         merge(arr, left, mid, right); // merge sub array
         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;
}
// Main function to implement timsort algorithm
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 << "The Original array- ";
   printArray(arr, n);
   // calling the timsortAlgo function to sort array
   timSortAlgo(arr, n);
   cout<<"After Sorting Array Using TimSort Algorithm- ";
   printArray(arr, n); // Calling print function
   return 0;
}