シェーカーソート
クラスソート
データ構造配列
最悪計算時間О(n2)

シェーカーソート (英: shaker sort) は、ソートのアルゴリズムの一つ。バブルソートを、効率がよくなるように改良したもの。別名は、双方向バブルソート、改良交換法[1]。

バブルソートではスキャンを一方向にしか行わないのに対し、シェーカーソートでは交互に二方向に行う。バブルソートと同じく安定な内部ソートで、最悪の場合の時間計算量はO(n2)である。
アルゴリズム

バブルソートで1回スキャンを行うと、最後の要素1個がスキャン範囲中最大であることが分かり次回のスキャン範囲を1狭めることができる。さらに、このスキャンの最後で連続してm個の要素の交換が行われていなければ、そのm個についてはソート済みであることが分かるので、次回のスキャン範囲をm狭めることができる。この工夫で、後半が殆ど整列済みのデータに対してバブルソートが高速に行えるようになる。

シェーカーソートはこれに加え、スキャン方向を毎回反転することにより、スキャン範囲を後方からだけではなく前方からも狭めるようにしたものである。挿入ソートのように、殆ど整列済みのデータに対しては高速に行うことができる。
実装例

C++言語による実装例を示す。#include <algorithm> // std::swaptemplate<typename T> void shaker_sort(T data[], int num_elements){ int top_index = 0; int bot_index = num_elements - 1; while (true) { int last_swap_index; /* 順方向のスキャン */ last_swap_index = top_index; for (int i = top_index; i < bot_index; i++) { if (data[i] > data[i+1]) { std::swap(data[i], data[i+1]); last_swap_index = i; } } bot_index = last_swap_index; /* 後方のスキャン範囲を狭める */ if (top_index == bot_index) break; /* 逆方向のスキャン */ last_swap_index = bot_index; for (int i = bot_index; i > top_index; i--) { if (data[i] < data[i-1]) { std::swap(data[i], data[i-1]); last_swap_index = i; } } top_index = last_swap_index; /* 前方のスキャン範囲を狭める */ if (top_index == bot_index) break; }}
動作例

t はスキャン範囲の先頭、b は末尾を表す。

初期データ: 8 4 3 7 6 5 2 1

1回目のスキャン終了後: (交換回数:7)4 3 7 6 5 2 1 8t b

2回目のスキャン終了後: (交換回数:6)1 4 3 7 6 5 2 8 t b

3回目のスキャン終了後: (交換回数:4)1 3 4 6 5 2 7 8 t b

4回目のスキャン終了後: (交換回数:4)1 2 3 4 6 5 7 8 t b

5回目のスキャン終了後: (交換回数:1)1 2 3 4 5 6 7 8 t b

6回目のスキャン終了後: (交換回数:0)1 2 3 4 5 6 7 8

合計交換回数:7+6+4+4+1+0=22 (バブルソートの場合22)
脚注[脚注の使い方]
出典^ シェーカーソートの意味(出典:デジタル大辞泉) - goo辞書

関連項目.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:#f9f9f9;display:flow-root}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}ウィキメディア・コモンズには、ソートアルゴリズムに関連するカテゴリがあります。

表

話

編

歴
ソート
理論

計算複雑性理論

ランダウの記号

全順序

リスト

安定性

ソーティングネットワーク

比較ソート（英語版）

整数ソート（英語版）

交換ソート

バブルソート

シェーカーソート

奇偶転置ソート

コムソート

ノームソート

クイックソート

選択ソート

選択ソート

ヒープソート

スムースソート

デカルト木ソート

トーナメントソート

挿入ソート

挿入ソート

シェルソート

ツリーソート

図書館ソート

ペイシェンスソート

マージソート

マージソート

多層マージソート

ストランドソート

非比較ソート

基数ソート

バケットソート

計数ソート

プロキシマップソート

鳩の巣ソート

バーストソート

ビーズソート

並行ソート

バイトニックソート

バッチャー奇偶マージソート

シェアソート

混成ソート

ティムソート

イントロソート

Jソート

アンシャッフルソート（英語版）

その他

トポロジカルソート

パンケーキソート

スパゲティソート

非効率的/
ユーモラスソート

ボゴソート

ストゥージソート

スリープソート

エラーソート

カテゴリ
.mw-parser-output .asbox{position:relative;overflow:hidden}.mw-parser-output .asbox table{background:transparent}.mw-parser-output .asbox p{margin:0}.mw-parser-output .asbox p+p{margin-top:0.25em}.mw-parser-output .asbox{font-size:90%}.mw-parser-output .asbox-note{font-size:90%}.mw-parser-output .asbox .navbar{position:absolute;top:-0.90em;right:1em;display:none}

この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。
.mw-parser-output .hlist ul,.mw-parser-output .hlist ol{padding-left:0}.mw-parser-output .hlist li,.mw-parser-output .hlist dd,.mw-parser-output .hlist dt{margin-right:0;display:inline-block;white-space:nowrap}.mw-parser-output .hlist dt:after,.mw-parser-output .hlist dd:after,.mw-parser-output .hlist li:after{white-space:normal}.mw-parser-output .hlist li:after,.mw-parser-output .hlist dd:after{content:" ・\a0 ";font-weight:bold}.mw-parser-output .hlist dt:after{content:": "}.mw-parser-output .hlist-pipe dd:after,.mw-parser-output .hlist-pipe li:after{content:" |\a0 ";font-weight:normal}.mw-parser-output .hlist-hyphen dd:after,.mw-parser-output .hlist-hyphen li:after{content:" -\a0 ";font-weight:normal}.mw-parser-output .hlist-comma dd:after,.mw-parser-output .hlist-comma li:after{content:"、";font-weight:normal}.mw-parser-output .hlist-slash dd:after,.mw-parser-output .hlist-slash li:after{content:" /\a0 ";font-weight:normal}.mw-parser-output .hlist dd:last-child:after,.mw-parser-output .hlist dt:last-child:after,.mw-parser-output .hlist li:last-child:after{content:none}.mw-parser-output .hlist dd dd:first-child:before,.mw-parser-output .hlist dd dt:first-child:before,.mw-parser-output .hlist dd li:first-child:before,.mw-parser-output .hlist dt dd:first-child:before,.mw-parser-output .hlist dt dt:first-child:before,.mw-parser-output .hlist dt li:first-child:before,.mw-parser-output .hlist li dd:first-child:before,.mw-parser-output .hlist li dt:first-child:before,.mw-parser-output .hlist li li:first-child:before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child:after,.mw-parser-output .hlist dd dt:last-child:after,.mw-parser-output .hlist dd li:last-child:after,.mw-parser-output .hlist dt dd:last-child:after,.mw-parser-output .hlist dt dt:last-child:after,.mw-parser-output .hlist dt li:last-child:after,.mw-parser-output .hlist li dd:last-child:after,.mw-parser-output .hlist li dt:last-child:after,.mw-parser-output .hlist li li:last-child:after{content:")\a0 ";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li:before{content:" "counter(listitem)" ";white-space:nowrap}.mw-parser-output .hlist dd ol>li:first-child:before,.mw-parser-output .hlist dt ol>li:first-child:before,.mw-parser-output .hlist li ol>li:first-child:before{content:" ("counter(listitem)" "}.mw-parser-output .navbar{display:inline;font-size:75%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}.mw-parser-output .infobox .navbar{font-size:88%}.mw-parser-output .navbox .navbar{display:block;font-size:88%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}