BohYoh.comトップページへ

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

戻る  

演習6-7の解答

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

// 演習6-7 // 単純挿入ソート(番兵法:配列の先頭要素は空いている) import java.util.Scanner; class InsertionSortCen {     //--- 単純挿入ソート(番兵法:配列の先頭要素は空いている)---//     static void insertionSort(int[] a, int n) {         for (int i = 1; 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 > 0a[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);                // 配列xを単純挿入ソート         System.out.println("昇順にソートしました。");         for (int i = 1; i <= nx; i++)             System.out.println("x[" + i + "]=" + x[i]);     } }


戻る