挿入ソート

はじめに

今まで標準ライブラリに実装されているソートを利用していたが、アルゴリズムをイチから勉強しなおそうと思った。

挿入ソートとは

１つずつ数字を取り出して、それをその時点ですでにソートされている並びの適切な位置に挿入するソート手法。

具体例と計算量

ソースコード

数字配列を受け取って、並び替えて返す関数を作成。

vector<long> insertSort(vector<long> v)
{
	long len = v.size();

	for (long i = 1; i < len; i++)
	{
		// 挿入しようとしている数字が比較対象より小さい限り入れ替え
		for (long j = i; j > 0; j--)
		{
			if (v[j] < v[j - 1])
			{
				long tmp = v[j];
				v[j] = v[j - 1];
				v[j - 1] = tmp;
			}
			else
			{
				break;
			}
		}
	}
	return v;
}

今後に向けてメモ

• 上述のコードだとvector<long>のソートしかできないため、string,vector<int>とか配列型なら何でもソートできるようにしたい(Template使うのかな？)
• 受け取った配列をソートして返すのではなく、実際のアドレスにアクセスして参照渡しをしたほうが無駄にメモリを使わない気がする