|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana) ・ カー ： [かー] 【名詞】 1. car 2. (n) car
シェーカーソートは、ソートのアルゴリズムの一つ。バブルソートを、効率がよくなるように改良したもの。 バブルソートではスキャンを一方向にしか行わないのに対し、シェーカーソートでは交互に二方向に行う。 バブルソートと同じく安定な内部ソートで、最悪の場合の時間計算量はO(n2)である。 == アルゴリズム == バブルソートで1回スキャンを行うと、最後の要素1個がスキャン範囲中最大であることが分かり次回のスキャン範囲を1狭めることができる。 さらに、このスキャンの最後で連続してm個の要素の交換が行われていなければ そのm個についてはソート済みであることが分かるので、次回のスキャン範囲をm狭めることができる。 この工夫で、後半が殆ど整列済みのデータに対してバブルソートが高速に行えるようになる。 シェーカーソートはこれに加え、スキャン方向を毎回反転することにより、スキャン範囲を後方からだけではなく前方からも狭めるようにしたものである。挿入ソートのように、殆ど整列済みのデータに対しては高速に行うことができる。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「シェーカーソート」の詳細全文を読む スポンサード リンク
|