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

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

🐠 概要

insertition-sort

🗻 特徴

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

🎂 AOJ問題

🍮 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