シェーカーソート 【cocktail shaker sort】

概要

シェーカーソート（cocktail shaker sort）とは、与えられたデータ列を大小などの順序通りになるよう並べ替えるソート(整列)アルゴリズムの一つで、バブルソートにおける要素の走査を交互に双方向に行うようにしたもの。バーテンダーがカクテルシェーカーを上下に振る動作になぞらえて “cocktail shaker sort” の名がついた。

バブルソートは端から順番に隣接する要素同士を比較・交換していくソート法で、先頭から末尾まで比較・交換を行うと、末尾に最も大きい（あるいは小さい）要素が来る。次は末尾を除いた残りの要素で同じ手順を行うと、末尾の隣に2番目に大きい（あるいは小さい）要素が来る。この走査を要素数-1回繰り返せばすべての要素が整列する。

バブルソートではこの走査を先頭から末尾へ、あるいは末尾から先頭へ常に同じ一方向に向かって行うが、シェーカーソートでは末尾に達したらその手前の要素から先頭へ、先頭に達したらその次の要素から末尾へ、交互に方向を入れ替えながら走査していく。開始位置が中央に達したら終了である。

シェーカーソートは整列したいデータ列以外の記憶領域を用意しなくて良い（インプレース）という特徴があり、同じ大きさの要素の順序が入れ替わらない安定ソートである。最良の場合（ほとんど整列済みの場合）の計算時間はO（n）と高速だが、最悪の場合の計算時間はO（n²）となる。計算量のオーダー自体はバブルソートと同等だが、若干効率が良いことが知られている。

この記事の著者 ： (株)インセプト IT用語辞典 e-Words 編集部
1997年8月より「IT用語辞典 e-Words」を執筆・編集しています。累計公開記事数は1万ページ以上、累計サイト訪問者数は1億人以上です。学術論文や官公庁の資料などへも多数の記事が引用・参照されています。