アルゴリズムの整理

1.アルゴリズムの基礎1.並べ替えを挿入する(Insertion-Sort)

for j=2 to A.length:
	key = A[j]
	//insert A[j] into the  sorted sequence A[1...j-1]
	i=j-1
	while i >0 and A[i]>key
		A[i+1] = A[i]
		i = i-1
	A[i+1]=key

原理:トランプの並び順に似ていますが、左手の札はA[1...j-1]で、右手に挿入する札A[j]です.残りはテーブルの上の札A[j+1...]です.
証明:循環不変式(loop invariants):初期化:まず循環を証明する前に成立します.j=2ですから、j-1=1です.サイクル開始前に、A[1...j-1](つまり、A[1]となります.)がソートされています.保持:ある反復が前に成立すると、次の反復も成立することを証明する必要がある(例:j＝8の前およびj＝8)終端:循環終了の出現を判断する性質証明が成立する.j=2,3,4...nは、n=n＋1でループが終了すると、列のA[1...n]は、元の配列のすべての要素と同じで、順序が既に並べられているので、アルゴリズムが成立する.
2.ポインタは配列またはオブジェクトの変数を表します.配列またはオブジェクトのデータのメモリアドレスを指します.(引用ではなく、参照はメモリアドレスに別名を付ける)e.g:xの属性をfとして設定します.yは同じオブジェクトを指しています.ポインタがオブジェクトを指していない場合、NILとなります.
3.時間複雑度挿入ソートの総運転時間:T(n)=1 n+1(n-1)+1*(n-1)+(t 2+...tn)+(t 2-1)+(t 2)+(t 2-1)+(tn-1)+1*(n-1)最適状況:n最悪状況:Thtanの平方