Javaで学ぶストゥージソートの実装方法とコード解説

ストゥージソート（Stooge Sort）は、再帰を利用したシンプルなソートアルゴリズムの一つです。実用性よりも教育的な目的で知られており、計算量は O(n^(log 3 / log 1.5)) ≒ O(n^2.71) とバブルソートよりも遅いという特徴があります。ここでは、Javaを使ってストゥージソートを実装する方法を、サンプルコードとともにわかりやすく解説します。

Javaによるストゥージソートの実装例

以下は、ストゥージソートをJavaで実装したプログラムです。

import java.io.*;
public class Demo {
   static void stooge_sort(int my_arr[], int l_val, int h_val){
      if (l_val >= h_val)
      return;
      if (my_arr[l_val] > my_arr[h_val]){
         int temp = my_arr[l_val];
         my_arr[l_val] = my_arr[h_val];
         my_arr[h_val] = temp;
      }
      if (h_val-l_val+1 > 2){
         int temp = (h_val-l_val+1) / 3;
         stooge_sort(my_arr, l_val, h_val-temp);
         stooge_sort(my_arr, l_val+temp, h_val);
         stooge_sort(my_arr, l_val, h_val-temp);
      }
   }
   public static void main(String args[]){
      int my_arr[] = {12, 34, 67, 91, 11, 0, 89, 102, 39};
      int n = my_arr.length;
      stooge_sort(my_arr, 0, n-1);
      System.out.println("The array after performing stooge sort is ");
      for (int i=0; i < n; i++)
      System.out.print(my_arr[i] + " ");
   }
}

実行結果

このプログラムを実行すると、コンソールに以下のようにソート済みの配列が出力されます。

The array after performing stooge sort is
0 11 12 34 39 67 89 91 102

コードの仕組みを解説

このプログラムの中核となるのは、Demo クラス内に定義された stooge_sort メソッドです。このメソッドは、対象となる配列と、ソート範囲の左端（l_val）・右端（h_val）のインデックスを引数として受け取ります。

まず、左端のインデックスが右端以上であれば、範囲内に要素が存在しないため処理を終了して何も返しません。次に、配列の左端の要素が右端の要素より大きい場合、両者を単純な入れ替え（スワップ）によって並べ替えます。

さらに、範囲内の要素数が3つより多い場合は、区間のサイズを3で割った値を基準に、stooge_sort メソッドを再帰的に呼び出します。具体的には「前半2/3の区間」「後半2/3の区間」「再度前半2/3の区間」の順に3回呼び出すことで、配列全体を段階的に整列させていきます。これがストゥージソート特有の再帰構造です。

mainメソッドでは、まず整数型の配列を定義し、その長さを変数 n に格納します。続いて、配列と両端のインデックス（0 と n-1）を渡して stooge_sort を呼び出し、ソート完了後の配列を for ループで順番に出力しています。

まとめ

ストゥージソートは、再帰呼び出しの流れやアルゴリズムの動作原理を理解するのに適した題材です。ただし計算量が大きいため、実際の開発ではクイックソートやマージソートなど、より効率的なソートアルゴリズムを選択するのが一般的です。学習用途として、ぜひこのコードを実際に動かして挙動を確認してみてください。