ノームソート

ノームソート（英: gnome sort）はソートアルゴリズムの一種で、挿入ソートに似ているが、要素の移動は挿入ではなくバブルソートのような一連の交換で行う。その名称の由来は、オランダのノームが一列に並んだ鉢植えの花をソートする話である。
非常に単純であり、入れ子のループも必要としない。時間計算量は O("n"2) だが、実際にソートしてみると挿入ソートと同程度の性能を発揮する。
このアルゴリズムでは、隣接する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という並びを昇順にソートする場合にループ内で起きていることを示す。