HIRASE CONNECTION WK

[C++] シェーカーソート

シェーカーソート（シェーカーソート、Shaker sort、カクテルソート、Cocktail sort、双方向バブルソート、bidirectional bubble sort）。

バブルソートの改良版。バブルソートで1回のループで昇順と降順を一度に並び替える。同じ要素の並びは変わらない安定ソート。

template <typename TElement, typename TSize>
void ShakerSort(TElement * data, const TSize size)
{
    TSize head = 0;
    TSize tail = size - 1;
    while (head < tail)
    {
        TSize swapPos = head;

        for (TSize i = head; i < tail; ++i)
        {
            TElement diff = data[i] - data[i+1];
            if (diff > 0)
            {
                data[i  ] = data[i+1];
                data[i+1] = diff + data[i];
                swapPos = i;
            }
        }

        tail = swapPos;

        for (TSize i = tail; i > head; --i)
        {
            TElement diff = data[i] - data[i+1];
            if (diff > 0)
            {
                data[i  ] = data[i+1];
                data[i+1] = diff + data[i];
                swapPos = i;
            }
        }
        {    // TSizeがunsigned型の場合、対策。
            TSize i = head;
            TElement diff = data[i] - data[i+1];
            if (diff > 0)
            {
                data[i  ] = data[i+1];
                data[i+1] = diff + data[i];
                swapPos = i;
            }
        }
        head = swapPos;
    }
}

投稿日時 : 2008年5月8日 2:33