|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana)
ノームソート（英: gnome sort）はソートアルゴリズムの一種で、挿入ソートに似ているが、要素の移動は挿入ではなくバブルソートのような一連の交換で行う。その名称の由来は、オランダのノームが一列に並んだ鉢植えの花をソートする話である〔Gnome sort page by Dick Grune〕。 :（試訳）「ノームソートは一般的なオランダのガーデンノーム（蘭: tuinkabouter）が使う技法に基づいている。以下がガーデンノームが植木鉢の列を並べ替える方法である。基本的に、ノームは自分の前に並んでいる植木鉢と後ろに並んでいる植木鉢を見る。もしそれらの順序が正しいなら、ノームは植木鉢一つ分だけ前に移動するが、そうでない場合は、それら二つの植木鉢の位置を交換してから、自分は植木鉢一つ分だけ後ろに移動する。境界条件： もし後ろに植木鉢がない場合ノームは前に移動する； もしノームの前に植木鉢がなかったら並べ替えは完了である。」 非常に単純であり、入れ子のループも必要としない。時間計算量は O(''n''2) だが、実際にソートしてみると挿入ソートと同程度の性能を発揮する。 このアルゴリズムでは、隣接する2つの要素の順序が正しくないときは、それらを交換する。この交換を行ったとき、「正しくない順序にある隣接要素」が新たに発生するのは、交換した要素の直前か直後だけであるという点に注視する。交換した要素よりも前の部分はまだ整列されていないという前提なので、交換した要素の直後のみを確認すればよいことになる。 また、処理対象全部を読み込む前にソートを開始できるため、標準入力やパイプラインで読み込みながら並行してソート処理が行えるという特徴もある(上の例でいうと、ノームが植木鉢を並べ替えている最中に、ノームよりも前に植木鉢を足していっても並び替えは問題なく完了する)。 == 擬似コード == 以下にノームソートのPascalベースの擬似コードを示す。 function gnomeSort(a) 実施例として4、2、7、3という並びを昇順にソートする場合にループ内で起きていることを示す。 * 4273 （初期状態） * 4273 （逆順なので交換する） * 2473 （交換したので前に戻る） * 2473 （端なので次に進む） * 2473 （正順なので次に進む） * 2473 （正順なので次に進む） * 2473 （逆順なので交換する） * 2437 （交換したので前に戻る） * 2437 （逆順なので交換する） * 2347 （交換したので前に戻る） * 2347 （正順なので次に進む） * 2347 （正順なので次に進む） * 2347 （正順なので次に進む） * 2347（最後まで調べたので終了） 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ノームソート」の詳細全文を読む スポンサード リンク
|