ノームソートで配列を並び替える

ノームソートを使用する

ノームソート (gnome sort / stupid sort) は、直感に沿った単純なルールだけで昇順へ整列させる比較ソートである。「庭のノームが並んだ植木鉢を、隣との大小関係を見ながら前後へ動きながら整える」様子になぞらえ、この名前が付いている説明がよくされている。

処理の状態は現在位置 pos（しばしば「ノームの足元」などと呼ぶ）だけでよいことから、状態機械として読みやすく、コードも短く書けるという利点がある。一方で、一般に最悪時間計算量は O(n²) であり、規模が大きいデータ向けではなく、概念的な説明や遊び的な題材として用いられることが多い。

pos = 0 から始める。配列の左端から眺めていく。
pos == 0 または A[pos] >= A[pos - 1] のとき：いま見ている並びがローカルに問題ないので 1ステップ進み、pos += 1 とする。
それ以外：隣との順序が逆なので 隣どうしを交換し、pos -= 1 してひとつ戻って再チェックする（より左側とも整合させる）。
pos == n になるまで繰り返す。

procedure gnome_sort(A)
  pos = 0
  while pos < length(A)
    if pos = 0 or A[pos] >= A[pos - 1] then
      pos = pos + 1
    else
      swap(A[pos], A[pos - 1])
      pos = pos - 1

交換が > だけでトリガされる実装では、等しい値の相対順序は変わらないため安定なソートとして扱える。追加の配列を使わなければ空間計算量は O(1) である。すでにソート済みの列では比較しながら右へ進むだけなので O(n)、逆順に近い並びでは前後への往復が多く O(n²) になる。

バブルのように端へ値を運ぶより「小さい不整合が出るたびにすぐその場で直しにいく」挙動が特徴で、単純ながら規模が増えると時間が読みにくくなる側面もある。教材としては状態の種類が少なく、コードと動きの対応を追いやすいソートアルゴリズムといえる。