シェーカーソート () は、ソートのアルゴリズムの一つ。バブルソートを、効率がよくなるように改良したもの。バブルソートではスキャンを一方向にしか行わないのに対し、シェーカーソートでは交互に二方向に行う。バブルソートと同じく安定な内部ソートで、最悪の場合の時間計算量はO(n)である。バブルソートで1回スキャンを行うと、最後の要素1個がスキャン範囲中最大であることが分かり次回のスキャン範囲を1狭めることができる。さらに、このスキャンの最後で連続してm個の要素の交換が行われていなければそのm個についてはソート済みであることが分かるので、次回のスキャン範囲をm狭めることができる。この工夫で、後半が殆ど整列済みのデータに対してバブルソートが高速に行えるようになる。シェーカーソートはこれに加え、スキャン方向を毎回反転することにより、スキャン範囲を後方からだけではなく前方からも狭めるようにしたものである。挿入ソートのように、殆ど整列済みのデータに対しては高速に行うことができる。C++言語による実装例を示す。t はスキャン範囲の先頭、b は末尾を表す。初期データ: 8 4 3 7 6 5 2 11回目のスキャン終了後: (交換回数:7)2回目のスキャン終了後: (交換回数:6)3回目のスキャン終了後: (交換回数:4)4回目のスキャン終了後: (交換回数:1)5回目のスキャン終了後: (交換回数:1)6回目のスキャン終了後: (交換回数:0)合計交換回数:7+6+4+1+1+0=19 (バブルソートの場合22)

出典:wikipedia