ノームソート 擬似コード

ウィキペディア

ノームソート

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/06/13 18:04 UTC 版)

擬似コード

以下にノームソートの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（最後まで調べたので終了）