挿入ソート

ホームアルゴリズム入門講座 > 挿入ソート

挿入ソート

挿入ソートの基本データ

挿入ソートのアルゴリズム

挿入ソートはバブルソートによく似たアルゴリズムです。バブルソートが後ろから整列するのに対して、挿入ソートは「暫定的に前から」整列します。

挿入ソートはまず、1番目と2番目のデータを比較し、2番目の方が小さければ交換します。次に、3番目のデータをその間に挿入します。

(元のデータ) : 3 2 1

(まず最初の2つを比較)
2 3 1
(3番目のデータと2番目のデータを比較)
2 1 3
(2番目のデータと1番目のデータを比較)
1 2 3

あたかも「1」が「2」の前に挿入されたかのように見える!!

挿入ソートの実装

using System;

namespace NewWorld
{
	class MainClass
	{
		public static void Main(string[] args)
		{
			int[] data = {6,3,8,5,4,7,9,2,1};
			int m;
			int count = 0;
			for(int i = 1; i < data.Length; i++)
			{
				for(int y = i; y > 0 && data[y-1] > data[y]; y--)
				{
					m = data[y-1];
					data[y-1] = data[y];
					data[y] = m;
					count++;
				}
				Console.Write("{0} roop: ",i);
				foreach(int num in data)
					Console.Write(num + " ");
				Console.WriteLine();
			}
			
			Console.WriteLine("{0} times",count);
		}
	}
}

挿入ソートがバブルソートに似ていながら、挿入ソートよりも早いのは for の評価式の中に理由があります。挿入ソートは「挿入」が終わったらその時点で繰り返しを終了するのです。

具体的に言えば、挿入ソートの「進行地点」は上のプログラムの変数 i で示されます。そして、i よりも前に挿入する値を挿入していくのです。ですが、挿入する値が常に最小である場合をのぞき、挿入する箇所は最初から i までのどこかにあります。挿入する箇所が決まったら、最初からその箇所までを比較する必要がなくなります。

このアルゴリズムによって、挿入ソートは「ほとんど整列されたデータを整列するのは早い」という特徴を持っています。

バブルソートとの比較

バブルソートと比較した場合、交換回数は同じですが、比較回数は違います。上のデータで計算した場合、バブルソートは64回、バブルソートの改良版は36回、挿入ソートは22回でした。

また、データを {1,2,4,3,5,6,7,8,9} という「ほとんど整列されたデータ」に変えて試してみたところ、バブルソートとその改良版は変わりませんでしたが、挿入ソートは1回でした。

挿入ソートは人間がならび変えをしていくパターンに近いアルゴリズムであるといえます。