シェーカーソート（シェーカーソート、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;
}
}