シェーカーソートのソースを表示

{{Infobox algorithm
|class=[[ソート]]
|image=[[ファイル:Sorting shaker sort anim.gif|視覚化したシェーカーソート]]
|data=[[配列]]
|time=''О(n²)''
|space=
|optimal=No
}}'''シェーカーソート''' ({{lang-en-short|shaker sort}}) は、[[ソート]]の[[アルゴリズム]]の一つ。[[バブルソート]]を、効率がよくなるように改良したもの。別名は、'''双方向バブルソート'''、'''改良交換法'''<ref>[https://dictionary.goo.ne.jp/word/シェーカーソート シェーカーソートの意味](出典:デジタル大辞泉) - [https://dictionary.goo.ne.jp goo辞書]</ref>。

バブルソートではスキャンを一方向にしか行わないのに対し、シェーカーソートでは交互に二方向に行う。バブルソートと同じく[[安定ソート|安定]]な内部ソートで、最悪の場合の[[計算複雑性理論|時間計算量]]は[[ランダウの記号|O(n<sup>2</sup>)]]である。

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

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

===実装例===
[[C++]]言語による実装例を示す。
<syntaxhighlight lang="cpp">
#include <algorithm> // std::swap

template<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;
    }
}
</syntaxhighlight>

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

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

1回目のスキャン終了後: (交換回数:7)
 4 3 7 6 5 2 1 8
 t           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)

== 脚注 ==
{{脚注ヘルプ}}
=== 出典 ===
{{Reflist}}

== 関連項目 ==
{{Commonscat|Sort algorithms|ソートアルゴリズム}}
{{ソート}}

{{Computer-stub}}
{{デフォルトソート:しええかあそおと}}
[[Category:ソート]]