挿入ソート(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

🖥 VULTRおすすめ

VULTR」はVPSサーバのサービスです。日本にリージョンがあり、最安は512MBで2.5ドル/月($0.004/時間)で借りることができます。4GBメモリでも月20ドルです。 最近はVULTRのヘビーユーザーになので、「ここ」から会員登録してもらえるとサービス開発が捗ります!

📚 おすすめの書籍