【Java】2種類の基本挿入法の実装

基本挿入法

大きい順または小さい順に並んでいる数列に、ある数を順に 比較しながらその数列に挿入し並び替えていくソートプログラムの１つこと。

これを2種類の方法で実装。
【方法①】
・挿入すべき位置を探す（ソートされている範囲の先頭から、挿入したいデータと値を比較し、挿入したいデータより大きい値が現われるまで右に移動する）

・右側にあるデータを1つ右に移動する（ソートされている範囲のうち、挿入位置より右側にあるデータを1つ右に移動して、挿入する場所を確保する）

・データを代入する（挿入する位置が空いたので、そこにデータを代入する）

【方法②】
方法①の比較方法を後ろから比較していくこと方法で、すべてのデータにアクセスする必要がなくなるため高速化を目的とした方法。

基本挿入法の実装コード

InsertionSortTest.java

public class InsertionSortTest {
    // 方法①
    static void insertion_sort1(int[] d) {
	int i,j,k;
        for (i = 1; i < d.length; i++ ) {
            int tmp = d[i];
            for (j = 0; j < i; j++) {
		if (d[j] > tmp) break;
            }
            for (k = i; k > j; k--) {
		d[k] = d[k-1];
            }
            d[j] = tmp;
        }
    }
    // 方法②
    static void insertion_sort2(int[] d){
  int i,j,k;
      for (i = d.length-2 ;i >= 0; i-- ){
        int tmp = d[i];
        for (j = d.length-1; j > i ; j-- ){
  if (tmp > d[j]) break;
        }
        for (k = i; k < j; k++) {
          d[k] = d[k+1];
        }
          d[j] = tmp;
      }
    }

    // 配列内のデータ列を表示する
    static void print_data(int[] d) {
        for(int i = 0; i < d.length; i++) System.out.print(d[i] + " ");
    }

    static int[] random_data(int num) {
      int romdata[] = new int[num];
      for (int i=0;i<num;i++){
      romdata[i] = (int)(Math.random()*10000);
          }
      return romdata;
    }

    public static void main(String[] args) {
        int[] data = random_data(1000);

        print_data(data);
        // 方法①を実装（方法②を実装したい場合は下記を切り替える）
        insertion_sort1(random_data(1000));
        print_data(data);
    }
}

timeコマンドで、プログラム自体の処理時間(秒)を比較してコードの処理時間の比較も可能。