HIRASE CONNECTION WK

programming collection

目次

Blog 利用状況

ニュース

あわせて読みたいブログパーツ

書庫

日記カテゴリ

Link Collection

[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

コメントを追加

No comments posted yet.
タイトル  
名前  
URL
コメント