【Java】ノームソートの実装方法をサンプルコード付きでわかりやすく解説

ノームソート（Gnome Sort）は、一度に1つの要素に注目し、その要素を本来あるべき位置へ移動させていくシンプルなソートアルゴリズムです。隣接する要素を比較しながら必要であれば交換し、条件が満たされるまで戻りながら整列を進めるのが特徴で、その動作が「地精（ノーム）が花鉢を並べ替える様子」に似ていることからこの名前が付けられました。

ここでは、Javaでノームソートを実装する具体的な例を紹介します。

サンプルコード

import java.util.Arrays;
public class Demo{
   static void gnome_sort(int my_arr[], int n){
      int index = 0;
      while (index < n){
         if (index == 0)
            index++;
         if (my_arr[index] >= my_arr[index - 1])
            index++;
         else{
            int temp = 0;
            temp = my_arr[index];
            my_arr[index] = my_arr[index - 1];
            my_arr[index - 1] = temp;
            index--;
         }
      }
      return;
   }
   public static void main(String[] args){
      int my_arr[] = { 34, 67, 89, 11, 0 , -21 };
      gnome_sort(my_arr, my_arr.length);
      System.out.println("The array after performing gnome sort on it is ");
      System.out.println(Arrays.toString(my_arr));
   }
}

実行結果

The array after performing gnome sort on it is 
[-21, 0, 11, 34, 67, 89]

コードの解説

「Demo」という名前のクラス内に、staticメソッド「gnome_sort」が定義されています。まず、変数「index」に0を代入し、indexが配列の長さnより小さい間、以下の処理を繰り返します。

• indexが0の場合：比較対象となる前の要素が存在しないため、indexを1つ進めます。
• 現在の要素が前の要素以上の場合：順序が正しいと判断できるため、そのままindexを1つ進めます。
• 現在の要素が前の要素より小さい場合：一時変数「temp」を使って隣接する2つの要素を交換し、indexを1つ戻します。これにより、小さい要素が少しずつ左側へ移動していきます。

mainメソッドでは、34、67、89、11、0、-21という値を持つint型配列を定義し、その配列と長さを引数として「gnome_sort」メソッドを呼び出します。ソート完了後、Arrays.toString()メソッドを使用して、整列済みの配列をコンソールに出力します。

ノームソートの計算量

ノームソートの平均計算量および最悪計算量はO(n²)です。一方で、すでにソート済みの配列に対しては各要素を一度通過するだけで済むため、最良計算量はO(n)となります。実装が非常に簡単な反面、大規模なデータセットには不向きであり、学習用途や小規模データの整列に適したアルゴリズムといえます。