[C++]マージインサートソートを実装する[アルゴリズム]

はじめに

今回はマージインサートソートをC++で実装します。

アルゴリズム

ここでは主な流れのみを説明するので細かい部分は後述します。
実際に昇順(1,2,3,4...)に並び替えるとしたら

分割パート

1. 与えられた数列に対して、隣同士でペアを作成する。
2. それぞれのペアのうち、大きい方の要素と小さい方の要素を取り出してそれぞれ数列を作成する。(以後それぞれLs、Ssと呼ぶ)
3. 作成された大きい方の数列の要素数が2以上なら、それに対して1~3の処理を行う。

挿入パート

分割パートで分割された後にLsは再帰的にマージインサートソートされるので挿入パートではLはソート済みとする。

1. SsはソートされたLが並び替えられたのと同じように並び替えられている。(ペアを作成してあるので)
2. ペアを解除
3. そのSに対してこの3の手順がn回目なら、Sの中のヤコブタール数の第n項の2倍の数番目の要素(以後E)を挿入する。
4. ペア作成時よりEは自分のペアより小さく、そしてそのペアはソートされているからそのペアより左側に挿入できることが保証されるので、その範囲でバイナリソート(二分探索法)をする。
5. Ssの中のEの1つ左の要素を新たなEとして4に戻る。もし、元のEの左に要素がなければ3に戻る。(繰り返すことですべて挿入しきる)

これにより再帰的にソートされる。
挿入パート3でヤコブタール数列の2倍の数でグルーピングすることで効率的なソートになる。(証明が分かる方がいたらコメントで教えていただきたいです。)
ヤコブタール数列とは: https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q10116781430

実装

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

/*結果を確認するための出力関数*/
void	printVec(std::vector<int>& vec)
{
	std::cout << "vec=";
	for (size_t i = 0; i < vec.size(); i++)
		std::cout << vec[i] << ", ";
	std::cout << std::endl;
}

/*ヤコブタール数列生成*/
std::vector<int>	makeJacobSeq()
{
	std::vector<int>	JacobSeq;

	/*今回はソートする要素数が100個なので第10項までで十分*/
	JacobSeq.push_back(0);
	JacobSeq.push_back(1);
	for (size_t i = 2; i < 10; i++)
		JacobSeq.push_back((2 * JacobSeq[i - 2]) + JacobSeq[i - 1]);
	return (JacobSeq);
}

/*マージインサートソート*/
void	mergeInsertionSort(std::vector<int>& vec)
{
	/*再帰終了条件*/
	if (vec.size() == 1)
		return ;
	std::map<int, int>	pairs; /*ペアを保存する辞書*/
	std::vector<int>	large; /*大きい方で構成される数列*/
	std::vector<int>	small; /*小さい方で構成される数列*/
	int					remain = 0; /*ペア作成での余り(-1なら余りなし)*/

	/*
	分割パート
	*/
	if (vec.size() % 2 == 1)
	{
		/*余りあり*/
		remain = vec.back();
		vec.pop_back();
	}

	for (size_t i = 0; i < vec.size(); i += 2)
	{
		/*ペア作成*/
		if (vec[i] >= vec[i + 1])
		{
			large.push_back(vec[i]);
			small.push_back(vec[i + 1]);
		}
		else
		{
			large.push_back(vec[i + 1]);
			small.push_back(vec[i]);
		}
		/*ペア保存*/
		pairs[large.back()] = small.back();
	}
	mergeInsertionSort(large);

	/*largeの並び方でsmallを並び替える*/
	small.clear();
	for (size_t i = 0; i < large.size(); i++)
		small.push_back(pairs[large[i]]);
	if (remain)
	{
		/*余りは小さい方の数列の末尾に*/
		small.push_back(remain);
	}

	/*
	挿入パート
	*/
	std::vector<int> JacobSeq = makeJacobSeq();
	size_t i = 0; /*ヤコブタール数列の使用回数*/
	int	sum = 0; /*前から数えた現在のグループまでの要素数の和(挿入していく要素のスタート位置)*/
	int pos = 0; /*挿入する要素の位置*/
	int lastSum = 0; /*前回のsum(挿入していく要素の最終位置)*/
	std::vector<int> tmpLarge = large; /*largeに挿入していく過程でposから元のlargeの要素がずれるので元の状態のtmp*/
	std::vector<int>::iterator largePairPos; /*ペアのlarge内での位置*/
	while (sum < small.size())
	{
		lastSum = sum;
		sum += 2 * JacobSeq[i];
		if (sum > small.size())
			sum = small.size();
		pos = sum - 1;
		while (pos >= lastSum)
		{
			/*挿入する要素のペアのlarge内での位置(元の位置からずれてる可能性がある)*/
			if (pos == small.size() - 1)
				largePairPos = large.end();
			else
				largePairPos = std::lower_bound(large.begin(), large.end(), tmpLarge[pos]);
			/*挿入位置を二分探索*/
			std::vector<int>::iterator insertPos = std::lower_bound(large.begin(), largePairPos, small[pos]);
			large.insert(insertPos, small[pos]); 
			pos--;
		}
		i++;
	}

	/*元のvecに結果を戻す*/
	vec = large;
}

int main(void)
{
	std::vector<int> vec = { 2448, 3450, 4172, 1428, 6985, 8647, 538, 968, 7765, 4694, \
	7983, 1342, 1407, 5805, 3598, 1089, 2127, 5716, 2837, 1444, 6555, 6277, 4484, 9738, 8601, \
	6860, 9133, 4143, 6289, 2000, 6586, 5146, 1567, 4737, 5154, 9374, 2521, 2503, 3901, 4704, \
	8184, 8434, 5702, 1439, 6173, 511, 2627, 8846, 7601, 2316, 4223, 105, 4639, 5208, 2442, \
	9741, 9200, 271, 5399, 2879, 6600, 6751, 7855, 2016, 9432, 9423, 5717, 9646, 1727, 5335, \
	8383, 5256, 8407, 1723, 835, 6189, 3827, 1757, 8301, 5843, 3306, 4667, 141, 8710, 3313, \
	5739, 3902, 3873, 4615, 8915, 6991, 8482, 5303, 5403, 9337, 4414, 4784, 7403, 8864, 3853 };

	mergeInsertionSort(vec);
	printVec(vec);
}

上記が100個のランダムな要素に対してマージインサートソートを行うコードである。
また、実行結果は以下である。

% c++ -std=c++11 main.cpp
% ./a.out
vec=105, 141, 271, 511, 538, 835, 968, 1089, 1342, 1407, 1428, \
1439, 1444, 1567, 1723, 1727, 1757, 2000, 2016, 2127, 2316, \
2442, 2448, 2503, 2521, 2627, 2837, 2879, 3306, 3313, 3450, \
3598, 3827, 3853, 3873, 3901, 3902, 4143, 4172, 4223, 4414, \
4484, 4615, 4639, 4667, 4694, 4704, 4737, 4784, 5146, 5154, \
5208, 5256, 5303, 5335, 5399, 5403, 5702, 5716, 5717, 5739, \
5805, 5843, 6173, 6189, 6277, 6289, 6555, 6586, 6600, 6751, \
6860, 6985, 6991, 7403, 7601, 7765, 7855, 7983, 8184, 8301, \
8383, 8407, 8434, 8482, 8601, 8647, 8710, 8846, 8864, 8915, \
9133, 9200, 9337, 9374, 9423, 9432, 9646, 9738, 9741,

終わりに

マージソート、インサートソートは触れたことがある方が多いですが、マージインサートソートはあまり有名ではないと思います。何か疑問等があればコメントにて受け付けます。