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

演習6-9の解答

　配列の要素数が多くなると、要素の挿入に要する比較・代入のコストは無視できなくなる。目的列はソート済みであるため、挿入すべき位置は２分探索法によって調べることができる。そのように変更したプログラムを作成せよ。
　なお、このソート法は、２分挿入ソート（binary insertion sort ）と呼ばれるアルゴリズムとして知られている。
※ただし、安定ではなくなることに注意せよ。

// 演習6-9
// ２分挿入ソート

import java.util.Scanner;

class BinInsertionSort {

   //--- ２分挿入ソート ---//
   static void binInsertionSort(int[] a, int n) {
      for (int i = 1; i < n; i++) {
         int key = a[i];
         int pl = 0;         // 探索範囲先頭の添字
         int pr = i - 1;   // 　 〃 　末尾の添字
         int pc;            // 　 〃 　中央の添字
         int pd;            // 挿入すべ位置の添字

         do {
            pc = (pl + pr) / 2;
            if (a[pc] == key)      // 探索成功
               break;
            else if (a[pc] < key)
               pl = pc + 1;
            else
               pr = pc - 1;
         } while (pl <= pr);
         pd = (pl <= pr) ? pc + 1 : pr + 1;

         for (int j = i; j > pd; j--)
            a[j] = a[j - 1];
         a[pd] = key;
      }
   }

   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];

      for (int i = 0; i < nx; i++) {
         System.out.print("x[" + i + "]：");
         x[i] = stdIn.nextInt();
      }

      binInsertionSort(x, nx);            // 配列xを２分挿入ソート

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

戻る