BohYoh.comトップページへ

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

戻る  

演習6-2の解答

パス1:
  6   4   3   7   1   9 + 8
  6   4   3   7   1 - 8   9
  6   4   3   7 + 1   8   9
  6   4   3 + 1   7   8   9
  6   4 + 1   3   7   8   9
  6 + 1   4   3   7   8   9
  1   6   4   3   7   8   9
パス2:
  1   6   4   3   7   8 - 9

  …中略…

比較は21回でした。
交換は8回でした。
 右のように比較・交換の過程を詳細に表示するプログラムを作成せよ。
 比較する二つの要素間には、交換を行う場合は'+'を、交換を行わない場合は'-'を表示すること。
 また、ソート終了時に、比較回数と交換回数を表示すること。

// 演習6-2 // 単純交換ソート(交換の詳細を表示) import java.util.Scanner; class BubbleSortEx {    //--- 配列の要素a[idx1]とa[idx2]を交換 ---//    static void swap(int[] a, int idx1, int idx2) {       int t = a[idx1]; a[idx1= a[idx2]; a[idx2= t;    }    //--- 単純交換ソート ---//    static void bubbleSort(int[] a, int n) {       int ccnt = 0;      // 比較回数       int scnt = 0;      // 交換回数       for (int i = 0; i < n - 1; i++) {          System.out.printf("パス%d:\n", i + 1);          for (int j = n - 1; j > i; j--) {             for (int m = 0; m < n - 1; m++)                System.out.printf("%3d %c" , a[m](m != j-1' ' :                                  (a[j - 1> a[j]) '+' '-');             System.out.printf("%3d\n", a[n - 1]);             ccnt++;             if (a[j - 1> a[j]) {                scnt++;                swap(a, j - 1, j);             }          }          for (int m = 0; m < n; m++)             System.out.printf("%3d  " , a[m]);          System.out.println();       }       System.out.println("比較は" + ccnt + "回でした。");       System.out.println("交換は" + scnt + "回でした。");    }    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();       }       bubbleSort(x, nx);            // 配列xを単純交換ソート       System.out.println("昇順にソートしました。");       for (int i = 0; i < nx; i++)          System.out.println("x[" + i + "]=" + x[i]);    } }


戻る