コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

「ノームソート」の版間の差分

出典: フリー百科事典『ウィキペディア(Wikipedia)』
削除された内容 追加された内容
Cewbot (会話 | 投稿記録)
m cewbot: 修正ウィキ文法 26: HTMLの<b>タグの使用
Cewbot (会話 | 投稿記録)
m Bot作業依頼: sourceタグをsyntaxhighlightタグに置換 (Category:非推奨のsourceタグを使用しているページ) - log
23行目: 23行目:
以下にノームソートの[[Pascal]]ベースの[[擬似コード]]を示す。<!--なお、このコードでは若干最適化してあり、変数 ''j'' を使ってノームが左に移動していった際に戻る場所を覚えておく。これによって無駄な繰り返しと比較を省いている。--><!--この状態だと、最適化したら挿入ソートと同一アルゴリズムになるので書き換え-->
以下にノームソートの[[Pascal]]ベースの[[擬似コード]]を示す。<!--なお、このコードでは若干最適化してあり、変数 ''j'' を使ってノームが左に移動していった際に戻る場所を覚えておく。これによって無駄な繰り返しと比較を省いている。--><!--この状態だと、最適化したら挿入ソートと同一アルゴリズムになるので書き換え-->


<source lang="pascal">
<syntaxhighlight lang="pascal">
procedure gnomeSort(a[0..size-1]);
procedure gnomeSort(a[0..size-1]);
begin
begin
40行目: 40行目:
end
end
end;
end;
</syntaxhighlight>
</source>


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

2020年7月5日 (日) 22:59時点における版

ノームソート
クラス ソート
データ構造 配列
最悪計算時間
最良計算時間
最悪空間計算量 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)が使う技法に基づいている。以下がガーデンノームが植木鉢の列を並べ替える方法である。基本的に、ノームは自分の前に並んでいる植木鉢と後ろに並んでいる植木鉢を見る。もしそれらの順序が正しいなら、ノームは植木鉢一つ分だけ前に移動するが、そうでない場合は、それら二つの植木鉢の位置を交換してから、自分は植木鉢一つ分だけ後ろに移動する。境界条件: もし後ろに植木鉢がない場合ノームは前に移動する; もしノームの前に植木鉢がなかったら並べ替えは完了である。」

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

このアルゴリズムでは、隣接する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(最後まで調べたので終了)

脚注

  1. ^ Gnome sort page by Dick Grune