【Unity/C#】シェーカーソートとは(コード付き)

シェーカーソートとは？

バブルソートを、効率がよくなるように改良したもの。別名は、双方向バブルソート。
場合によっては普通のバブルソートより遅くなります。

アルゴリズム

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

実行結果

サンプルコード

bool swapFlag = false;
int[] ShakerSort(int[] _array)
{
    while (true)
    {
        swapFlag = false;
        //配列の回数分回す
        for (int i = 0; i < _array.Length-1; i++)
        {
            //比較元より大きければ入れ替え
            if (_array[i] > _array[i + 1])
            {
                int x = _array[i];
                _array[i] = _array[i + 1];
                _array[i + 1] = x;
                swapFlag = true;
            }
        }
        for (int i = _array.Length - 1; i > 0; i--)
        {
            //比較元より大きければ入れ替え
            if (_array[i] < _array[i - 1])
            {
                int x = _array[i];
                _array[i] = _array[i - 1];
                _array[i - 1] = x;
                swapFlag = true;
            }
        }
            //一度も入れ替え処理が通らなければ
        if (swapFlag==false)
        {
            break;
        }
    }
        //Sortした結果を返す
    return _array;
}

まとめ

まだまだ早くなりますがとりあえずこれがシェーカーソートとなります。
時間があり次第これを改善したシェーカーソートを載せます。