ノームソート

ノームソート

クラス	ソート
データ構造	配列
最悪計算時間	$O(n^{2})$
最良計算時間	$O(n)$
最悪空間計算量	$O(1)$ auxiliary

ノームソート（英: gnome sort）はソートアルゴリズムの一種で、挿入ソートに似ているが、要素の移動は挿入ではなくバブルソートのような一連の交換で行う。その名称の由来は、オランダのノームが一列に並んだ鉢植えの花をソートする話である。

Gnome Sort is based on the technique used by the standard Dutch Garden Gnome (Du.: tuinkabouter). Here is how a garden gnome sorts a line of flower pots. Basically, he looks at the flower pot next to him and the previous one; if they are in the right order he steps one pot forward, otherwise he swaps them and steps one pot backwards. Boundary conditions: if there is no previous pot, he steps forwards; if there is no pot next to him, he is done.

—Dick Grune

（試訳）「ノームソートは一般的なオランダのガーデンノーム（蘭: tuinkabouter）が使う技法に基づいている。以下がガーデンノームが植木鉢の列を並べ替える方法である。基本的に、ノームは自分の前に並んでいる植木鉢と後ろに並んでいる植木鉢を見る。もしそれらの順序が正しいなら、ノームは植木鉢一つ分だけ前に移動するが、そうでない場合は、それら二つの植木鉢の位置を交換してから、自分は植木鉢一つ分だけ後ろに移動する。境界条件：　もし後ろに植木鉢がない場合ノームは前に移動する；　もしノームの前に植木鉢がなかったら並べ替えは完了である。」

非常に単純であり、入れ子のループも必要としない。時間計算量は O(n²) だが、実際にソートしてみると挿入ソートと同程度の性能を発揮する。

このアルゴリズムでは、隣接する2つの要素の順序が正しくないときは、それらを交換する。この交換を行ったとき、「正しくない順序にある隣接要素」が新たに発生するのは、交換した要素の直前か直後だけであるという点に注視する。交換した要素よりも前の部分はまだ整列されていないという前提なので、交換した要素の直後のみを確認すればよいことになる。

また、処理対象全部を読み込む前にソートを開始できるため、標準入力やパイプラインで読み込みながら並行してソート処理が行えるという特徴もある(上の例でいうと、ノームが植木鉢を並べ替えている最中に、ノームよりも前に植木鉢を足していっても並び替えは問題なく完了する)。

擬似コード

以下にノームソートのPascalベースの擬似コードを示す。

procedure gnomeSort(a[0..size-1]);
  begin
    i := 1;
    while i < size do
      if a[i-1] <= a[i] then // 降順にソートする場合は >= で比較する
        begin
          i := i + 1; // 正順なので次に進む
        end
      else
        begin
          swap(a[i-1], a[i]); // 逆順なので交換する
          i := i - 1; // 交換したので前に戻る
          if i = 0 then
            i := i + 1; // 端なので次に進む
        end
  end;

実施例として4、2、7、3という並びを昇順にソートする場合にループ内で起きていることを示す。

• 4273 （初期状態）
• 4273 （逆順なので交換する）
• 2473 （交換したので前に戻る）
• 2473 （端なので次に進む）
• 2473 （正順なので次に進む）
• 2473 （正順なので次に進む）
• 2473 （逆順なので交換する）
• 2437 （交換したので前に戻る）
• 2437 （逆順なので交換する）
• 2347 （交換したので前に戻る）
• 2347 （正順なので次に進む）
• 2347 （正順なので次に進む）
• 2347 （正順なので次に進む）
• 2347（最後まで調べたので終了）