シェーカーソート（シェーカーソート、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;
}
}
ハトの巣ソート（ピジョンソート、Pigeon sort）。
いまいち理解できていないので、Wikipedia様に丸投げ→→「Pigeonhole sort」。（ 18:06, 19 March 2008版には擬似コードもあり。）
メモリは食うけど、ソートは馬鹿早い。同じ要素の並びは変わらない安定ソート。
追記＠2008-05-12T23:39+09:00：新しいバージョンをアップ。
/* データはユニークである必要があります。 */
template<typename TElement, typename TSize>
void PigeonholeSort(TElement * data, const TSize size)
{
TElement min = data[0];
TElement max = min;
for (TSize i = 1; i < size; ++i) {
min = data[i] < min ? data[i] : min;
max = data[i] > max ? data[i] : max;
}
TSize range = max - min + 1;
TElement * pigeonholes = new TElement[range];
for (TSize i = 0; i < range; ++i)
pigeonholes[i] = 0; /* memsetで十分。 */
for (TSize i = 0; i < size; ++i)
pigeonholes[data[i]-min] = data[i];
TSize dataPos = 0;
for (TSize i = 0; i < range; ++i)
if (pigeonholes[i] != 0)
data[dataPos++] = i + min;
delete[] pigeonholes;
}
追記@2008-05-08T17:19+09:00：下記のコードはちょっと間違えています。そのうち修正しますので、くれぐれも参考にしないよう、お願いします。
#include <map>
template<typename TElement, typename TSize>
void PigeonholeSort(TElement * data, const TSize size)
{
typedef std::map<TElement, std::vector<TElement> > TMap;
TMap pigeonholes;
for (TSize i = 0; i < size; ++i)
pigeonholes[data[i]].push_back(data[i]);
TSize dataPos = 0;
const TMap::const_iterator end = pigeonholes.end();
for (TMap::iterator it = pigeonholes.begin(); it != end; ++it)
{
const TMap::value_type & pigeonhole = *it;
const TSize size = pigeonhole.second.size();
for (TSize i = 0; i < size; ++i)
{
data[dataPos++] = pigeonhole.first;
}
}
}
選択ソート（直接選択ソート、Selection sort）。
一番小さいのを選んで、先頭へ。次に小さいのを選んで2番目に・・・と並べる。一般的には、同じ要素の並びが変わってしまう不安定ソート。
template<typename TElement, typename TSize>
void SelectionSort(TElement * data, const TSize size)
{
TSize tail = size - 1;
for (TSize head = 0; head < tail; ++head)
{
TElement * pMin = (data + head);
for (TSize pos = head + 1; pos < size; ++pos)
if (data[pos] < *pMin) pMin = (data + pos);
if (data + head != pMin)
{
TElement temp = data[head];
data[head] = *pMin;
*pMin = temp;
}
}
}