ノームソート

ノームソート

Gnome ソートの視覚化
クラス	ソートアルゴリズム
データ構造	配列
最悪の場合の パフォーマンス	${\displaystyle O(n^{2})}$
最高の パフォーマンス	${\displaystyle O(n)}$
平均的 なパフォーマンス	${\displaystyle O(n^{2})}$
最悪の場合の 空間複雑度	${\displaystyle O(1)}$補助

ノームソート（別名：愚かなソート）は、ネストされたループを使用しない挿入ソートの ソートアルゴリズムのバリエーションです。ノームソートは、もともとイランのコンピュータ科学者ハミド・サルバジ＝アザド（シャリフ工科大学のコンピュータサイエンスとエンジニアリングの教授）^{[1]によって2000年に提案されました。このソートは最初は}愚かなソート^{[2] （}ボゴソートと混同しないでください）と呼ばれていましたが、後にディック・グルーネによって説明され、ノームソートと名付けられました。^[3]

Gnome ソートは、挿入ソートと同数以上の比較を実行し、同じ漸近的な実行時間特性を持っています。Gnome ソートは、ソートされたリストを 1 要素ずつ構築し、一連のスワップで各項目を適切な場所に移動することで機能します。平均実行時間はO ( n ² ) ですが、リストが最初からほぼソートされている場合はO ( n )に近づく傾向があります。 ^{[4] [注 1]}

ディック・グルーネは、この選別方法について次のような物語で説明している。^[3]

ノームソートは、標準的なオランダのガーデンノーム(Du.: tuinkabouter)が使用する手法に基づいています。
ガーデンノームが一列に並んだ植木鉢をソートする方法は次のとおりです。
基本的に、ノームは隣の植木鉢と前の植木鉢を見て、正しい順序であれば 1 つずつ前に進み、そうでない場合は植木鉢を入れ替えて 1 つずつ後ろに進みます。
境界条件: 前の植木鉢がなければ前に進み、隣に植木鉢がなければこれで完了です。

—  「Gnome Sort - 最もシンプルなソートアルゴリズム」Dickgrune.com

以下は、ゼロベースの配列を使用した gnome ソートの疑似コードです。

 手順gnomeSort(a[]):
   位置:= 0
   pos < length(a)
       の場合: pos == 0またはa[pos] >= a[pos-1]の場合:
           位置:=位置+1
       そうでない場合:
            a[pos]とa[pos-1]を入れ替える
           位置:=位置-1

ソートされていない配列 a = [5, 3, 2, 4] が与えられた場合、gnome sort は while ループ中に次の手順を実行します。現在の位置は太字で強調表示され、変数の値として示されますpos。

Wikibookアルゴリズム実装には、Gnomeソートに関するページがあります。

• ノームソート