単純挿入整列法

応用情報のための勉強で出てくる整列アルゴリズム。
文字だけ見ててもイメージがつき難いから、一度実装してみようかと。

さっそく実装

実は、これが生まれて初めてのpythonプログラム。

def insertsort(data):
	l=len(data) #データ数を取得
	for i in range(0,l-1): 
		a=data[i+1]		#aに未整列の一番左側の数を代入
		 
		for j in range(0,i+2):	#0≦j≦i+1で
			if data[j]>a:   #aよりも大きいdata[j]があったら
				break   #breakする。なければ、j=i+1
		
		while j<=i+1:           
			tmp=data[j]     #tmpにdata[j]を一時的に格納し
			data[j]=a       #data[j]をaにする
			a=tmp           #aにtmpをいれて、次へ
			j+=1

思ったよりも手こずったのは、range()の使い方に慣れてなかったから。
range(0,5)ってやると、0≦x＜5って意味になるんだな。つまり、5は入らない。

オーダ（計算量）

最悪、という記述を目にする。
正直、その本質は理解していない。
また別に、オーダについても勉強しなければいけないな。
oっていうと、ランダウの記号を思い出すのだけれど、おんなじ意味なのかしら。

ちなみに

平成20年度秋期のソフトウェア開発技術者試験の問題11にて、単純挿入整列法に関する出題がされている。

　整列済みの列の末尾から比較して、次の要素の挿入位置を決める単純挿入整列法について考える。昇順に整列済みの大きさnのデータ列を、改めて昇順に整列する処理を行う場合の比較回数のオーダは、どれか。
ア：、イ：、ウ：、エ：

答えは、ア
僕の解釈では、整列済みであるために入れ替えが発生せず、その分、オーダはnで済んでいるってことなのかなと。

参考資料

平成21年度[春期][秋期] 応用情報技術者 合格教本

プログラミングの宝箱 アルゴリズムとデータ構造 (C magazine)