はしがき
プログラミング初心者がアルゴリズムを片端から実装していこうという記事.
今回は挿入ソートをC,Java,Ruby,Pythonで記述.
コードに改善すべき点がありましたら,ご教授いただけると幸いです.
挿入ソートの特徴
・要素数が少ない配列に対して効果的
・ほぼ整列済み、または重複した要素が多い配列に対して効果的
（要素の入れ替え回数が減るため）
・平均計算量1は$O$($n^2$) 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