挿入ソート実装

#はしがき
プログラミング初心者がアルゴリズムを片端から実装していこうという記事.
今回は挿入ソートをC,Java,Ruby,Pythonで記述.
コードに改善すべき点がありましたら,ご教授いただけると幸いです.

#挿入ソートの特徴
・要素数が少ない配列に対して効果的
・ほぼ整列済み、または重複した要素が多い配列に対して効果的
　（要素の入れ替え回数が減るため）
・平均計算量¹は$O$($n^2$)　²
　（平均でn個の要素それぞれをnの定数倍回入れ替えるため）

#C言語

/* sizeは配列の大きさ */
void insertionSort(int data[10], int size) {
	int i, j;
	for(i = 1; i < size; i++) {
		j = i;
		while(j > 0 && data[j - 1] > data[j]) {
			swap(&data[j - 1], &data[j]);
			j--; 
		}
	}
}

void swap(int *a, int *b) {
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

#Java

public static void insertionSort(int[] data) {	
	int i, j;
	for(i = 1; i < data.length; i++) {
        j = i;
        while(j > 0 && data[j - 1] > data[j]) {
            swap(data, j);
            j--; 
        }
    }
}

public static void swap(int[] data, int j) {
	int tmp;
	tmp = data[j];
	data[j] = data[j - 1];
	data[j - 1] = tmp;
}

#Ruby

def insertionSort(data)
	(1...data.length).each do |i|
		j = i
		while j > 0 && data[j - 1] > data[j]
			data[j - 1], data[j] = data[j], data[j - 1]
			j -= 1
		end
	end
end

#Python

def insertionSort(data):
	for i in range(1, len(data)):
		j = i
		while j > 0 and data[j - 1] > data[j]:
				data[j - 1], data[j] = data[j], data[j - 1]
				j -=1

#気づいたこと
・Javaの参照型変数は"String","Array","Class"
・Ruby,Pythonにおいて要素の入れ替えは1行で済む
・Rubyのfor文はeachメソッドとして解釈される
　(eachメソッドが変更されるとfor文の挙動も変わる)
・Rubyなどにおいて"&&"と"and"は異なる
　参考：&&とandの違い

#参考文献・サイト

• 『アルゴリズムリファレンス』,オライリージャパン，2010年4月
• 原隆浩・水田智史・大河剛直,『未来へつなぐ デジタルシリーズ 10 アルゴリズムとデータ構造』, 共立出版, 2012 年 6 月
• ソースコード探険隊
  https://www.codereading.com/algo_and_ds/algo/insertion_sort.html

1. 計算量：アルゴリズムの評価基準.構成命令をもとに求める. ↩

2. オーダー記法：計算量を示す記法.最も次数の高い項以外の項と係数は無視する. ↩