ノームソートのソースを表示

{{Infobox algorithm
|class=[[ソート]]
|image=[[File:Sorting_gnomesort_anim.gif]]
|data=[[配列]]
|time=<math>O(n^2)</math>
|best-time=<math>O(n)</math>
|average-time= <!--?-->
|space= <math>O(1)</math> auxiliary
|optimal= No
}}'''ノームソート'''（[[英語|英]]: gnome sort）は[[ソート]][[アルゴリズム]]の一種で、[[挿入ソート]]に似ているが、要素の移動は挿入ではなく[[バブルソート]]のような一連の交換で行う。その名称の由来は、オランダの[[ノーム (妖精)|ノーム]]が一列に並んだ鉢植えの花をソートする話である<ref>[http://dickgrune.com/Programs/gnomesort.html Gnome sort page] by Dick Grune</ref>。

{{quote|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.|[http://dickgrune.com/Programs/gnomesort.html Dick Grune]}}

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

非常に単純であり、入れ子のループも必要としない。時間計算量は [[ランダウの記号|O]](''n''<sup>2</sup>) だが、実際にソートしてみると[[挿入ソート]]と同程度の性能を発揮する。

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

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

== 擬似コード ==
以下にノームソートの[[Pascal]]ベースの[[擬似コード]]を示す。<!--なお、このコードでは若干最適化してあり、変数 ''j'' を使ってノームが左に移動していった際に戻る場所を覚えておく。これによって無駄な繰り返しと比較を省いている。--><!--この状態だと、最適化したら挿入ソートと同一アルゴリズムになるので書き換え-->

<syntaxhighlight lang="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;
</syntaxhighlight>

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

* 4273 （初期状態）
* <u>4'''2'''</u>73 （逆順なので交換する）
* <u>2'''4'''</u>73 （交換したので前に戻る）
* <u>'''2'''</u>473 （端なので次に進む）
* <u>2'''4'''</u>73 （正順なので次に進む）
* 2<u>4'''7'''</u>3 （正順なので次に進む）
* 24<u>7'''3'''</u> （逆順なので交換する）
* 24<u>3'''7'''</u> （交換したので前に戻る）
* 2<u>4'''3'''</u>7 （逆順なので交換する）
* 2<u>3'''4'''</u>7 （交換したので前に戻る）
* <u>2'''3'''</u>47 （正順なので次に進む）
* 2<u>3'''4'''</u>7 （正順なので次に進む）
* 23<u>4'''7'''</u> （正順なので次に進む）
* 2347（最後まで調べたので終了）

== 脚注 ==
{{Reflist}}

{{ソート}}
{{DEFAULTSORT:のむそと}}
[[Category:ソート]]