C++でストゥージソートを実装する方法：再帰的ソートアルゴリズムの解説とサンプルコード

ストゥージソート（Stooge Sort）は、与えられたデータを並べ替えるための再帰的なソートアルゴリズムです。配列をそれぞれ全体の2/3ずつが重なり合う2つの部分に分割し、「前半部分のソート → 後半部分のソート → 再び前半部分のソート」という3段階の手順で整列を行います。

このアルゴリズムの最悪計算量は O(n^2.7095) であり、バブルソート（O(n²)）よりも遅いという特徴があります。実用性は低いものの、再帰処理やアルゴリズムの学習教材として知られています。

アルゴリズムの手順

Begin
   データを入力として受け取る。
   データ配列 'a' と要素数 'n' を引数として StoogeSort() 関数を呼び出す。
   再帰的なアプローチでソートを実装する。
   配列を「先頭から2/3の要素」をパートI、「末尾から2/3の要素」をパートII に分割する。
   パートI、パートII、そして再度パートI の順に StoogeSort() へ渡す。
   それ以上分割できない長さの場合、a[end] < a[start] であれば先頭と末尾の要素を交換する。
   main に戻り、結果を表示する。
End.

サンプルコード

#include<iostream>
using namespace std;
void StoogeSort(int a[],int start, int end) {
   int temp;
   if(end-start+1 > 2) {
      temp = (end-start+1)/3;
      StoogeSort(a, start, end-temp);
      StoogeSort(a, start+temp, end);
      StoogeSort(a, start, end-temp);
   }
   if(a[end] < a[start]) {
      temp = a[start];
      a[start] = a[end];
      a[end] = temp;
    }
}
int main() {
   int m, i;
   cout<<"\nソートするデータ要素の個数を入力してください: ";
   cin>>m;
   int arr[m];
   for(i = 0; i < m; i++) {
      cout<<"要素 "<<i+1<<" を入力: ";
      cin>>arr[i];
   }
   StoogeSort(arr, 0, m-1);
   cout<<"\nソート後のデータ ";
   for (i = 0; i < m; i++)
      cout<<"->"<<arr[i];
   return 0;
}

実行結果

ソートするデータ要素の個数を入力してください: 4
要素 1 を入力: 6
要素 2 を入力: 7
要素 3 を入力: 3
要素 4 を入力: 2
ソート後のデータ ->2->3->6->7

コードのポイント

• 再帰構造： 要素数が3より大きい間、区間の2/3に相当する部分に対して3回の再帰呼び出しを行います。
• 境界処理： 分割できなくなった区間では、先頭と末尾の要素を比較し、必要であれば交換します。
• 計算量： 最悪ケースで O(n^2.7095) となり、効率面ではクイックソートやマージソートに大きく劣ります。

ストゥージソートは実務で使われることはほとんどありませんが、再帰の動作原理やアルゴリズムの計算量分析を学ぶうえで興味深い題材となります。ぜひ実際にコードを動かして、その挙動を確認してみてください。