ノームソート

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
ノームソート
Sorting gnomesort anim.gif
クラス ソート
データ構造 配列
最悪計算時間 O(n^2)
最良計算時間 O(n)
最悪空間計算量 O(1) auxiliary

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

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.

(試訳)「ノームソートは、いわゆるオランダのガーデンノーム(蘭: tuinkabouter)が使っていた技法に基づいている。ガーデンノームが一列の植木鉢をソートする方法を紹介しよう。ノームは基本的に目の前にある植木鉢とその1つ前の植木鉢を見る。その順序が正しいなら、ノームは後ろの植木鉢に移動し、そうでない場合は二つの植木鉢の位置を交換し、前の植木鉢に移動する。ただし、前に植木鉢がない場合は後ろに移動する。最後尾まで移動したら、完了である。

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

このアルゴリズムでは、隣接する2つの要素の順序が正しくないときは、それらを交換する。この交換を行ったとき、新たな正しくない順序が発生する可能性があるのは、その直後や直前だけだという利点がある。現在位置より先の部分の順序が正しいとは仮定していないので、交換を行った直前の位置だけをチェックすればよい。

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

擬似コード[編集]

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

 function gnomeSort(a[0..size-1]) {
  i := 1;
  while i < size do
    if a[i-1] <= a[i] # 降順にソートする場合は >= で比較する
       then begin
        i := i + 1; # 正しく並んでいるので何もせずに次に進む
       end
    else
      begin
        swap a[i-1] and a[i]; # 順序が間違っているので交換
        i := i - 1; # 交換したので前に戻る
        if i = 0
          i := i + 1 # 先頭なので戻るのは取りやめ
          i := i + 1 # 既に交換して順序は正しいので次に進む
         end
 }

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

  • 4273 (初期状態)
  • 4273 (逆順なので交換する)
  • 2473 (交換したが、先頭なので戻らずに次に進む)
  • 2473 (正順なのでそのままにして次に進む)
  • 2473 (逆順なので交換する)
  • 2437 (交換したので前に戻る)
  • 2437 (逆順なので交換する)
  • 2347 (交換したので前に戻る)
  • 2347 (正順なのでそのままにして次に進む)
  • 2347 (正順なのでそのままにして次に進む)
  • 2347 (正順なのでそのままにして次に進む)
  • 2347 (終端まで調べたので終了)

脚注[編集]

  1. ^ Gnome sort page by Dick Grune