BohYoh.comトップページへ

Javaによるアルゴリズムとデータ構造

戻る  

演習6-8の解答

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

// 演習6-8 // 2分挿入ソート import java.util.Scanner; class BinInsertionSort {     //--- 2分挿入ソート ---//     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 + pr2;                 if (a[pc== key)        // 探索成功                     break;                 else if (a[pc< key)                     pl = pc + 1;                 else                     pr = pc - 1;             while (pl <= pr);             pd = (pl <= pr? pc + : 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("2分挿入ソート");         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を2分挿入ソート         System.out.println("昇順にソートしました。");         for (int i = 0; i < nx; i++)             System.out.println("x[" + i + "]=" + x[i]);     } }


戻る