アルゴリズムの勉強: 挿入ソート(Insertition Sort)[AOJ ALDS1_1_A][JAVA][Ruby]

今回は、『挿入ソート ALDS1_1_A』についての記事です。JavaとRubyでのサンプルソースを載せておきます。


概要

insertition-sort

特徴

  • 要素が少ないか、最初から集まりが「ほぼ整列」した状態でのソートが早い(部分整列)
  • ランダムなデータに対して効率が悪い
  • 要素1つ分を蓄えるのに必要なメモリがあればよい
  • 大量のメモリ移動が発生する

AOJ

挿入ソート ALDS1_1_A

Javaのサンプルコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.lang.System;
class Main {
public static void main(String[] a) throws Exception {
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(r.readLine());
String[] str = r.readLine().split(" ");
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(str[i]);
}
int v, j;
printArray(n, arr);
for (int i = 1; i < n; i++) {
v = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > v) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = v;
printArray(n, arr);
}
}
private static void printArray(int n, int[] arr) {
StringBuilder s;
s = new StringBuilder();
for (int i = 0; i < n; i++) {
s.append(arr[i]);
if (i != n -1) { s.append(" "); }
}
System.out.println(s);
}
}

Rubyのサンプルコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
while n = gets.to_i
break if n == 0
arr = gets.split(' ').map(&:to_i)
0.upto(arr.size - 1) do |i|
v = arr[i]
j = i - 1
while j >= 0 && arr[j] > v
arr[j+1] = arr[j]
j -= 1
end
arr[j+1] = v
puts arr.join(' ')
end
end