シェーカーソート

シェーカーソート

クラス	ソート
データ構造	配列
最悪計算時間	О(n²)

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

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

アルゴリズム

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

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

実装例

C++言語による実装例を示す。

#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;
    }
}

動作例

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)