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


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

🗻 概要

insertition-sort

🐠 特徴

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

🗽 AOJ問題

挿入ソート ALDS1_1_A

😎 Javaコード

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] tmp = br.readLine().split(" ");
int[] arr = Arrays.asList(tmp).stream().mapToInt(x -> Integer.parseInt(x)).toArray();
printIntArray(arr);
for (int i = 1; i < n; i++) {
int v = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > v) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = v;
printIntArray(arr);
}
}
private static void printIntArray(int[] arr) {
StringBuilder s = new StringBuilder();
for (int i = 0; i < arr.length; i++) {
s.append(arr[i]);
if (i < arr.length - 1) {
s.append(" ");
}
}
System.out.println(s.toString());
}
}

😸 Rubyコード

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

📚 おすすめの書籍