新・明解Javaで学ぶアルゴリズムとデータ構造

演習6-8の解答

　配列の先頭要素a [0]が未使用でデータがa [1]以降に格納されていれば、a [0]を番兵とすることによって、挿入処理の終了条件を緩和できる。
　このアイディアに基づいて単純挿入ソートを行うメソッドを作成せよ。

// 演習6-8
// 単純挿入ソート（番兵法：配列の先頭要素は空いている）

import java.util.Scanner;

class InsertionSortCen {

   //--- 単純挿入ソート（番兵法：配列の先頭要素は空いている）---//
   static void insertionSort(int[] a, int n) {
      for (int i = 2; i < n; i++) {
         int tmp = a[0] = a[i];
         int j = i;
         for ( ; a[j - 1] > tmp; j--)
            a[j] = a[j - 1];
         if (j > 0) a[j] = tmp;
      }
   }

   public static void main(String[] args) {
      Scanner stdIn = new Scanner(System.in);

      System.out.println("単純挿入ソート");
      System.out.print("要素数：");
      int nx = stdIn.nextInt();
      int[] x = new int[nx + 1];            // 1個余分に生成

      for (int i = 1; i <= nx; i++) {      // x[1]～x[nx]に読み込む
         System.out.print("x[" + i + "]：");
         x[i] = stdIn.nextInt();
      }

      insertionSort(x, nx + 1);            // 配列xを単純挿入ソート

      System.out.println("昇順にソートしました。");
      for (int i = 1; i <= nx; i++)
         System.out.println("x[" + i + "]＝" + x[i]);
   }
}

戻る