BohYoh.comトップページへ

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

戻る  

演習6-5の解答

 以下に示すデータの並びをソートすることを考えよう。
  9 1 3 4 6 7 8
 ほぼソート済みであるにもかかわらず、最大の要素9が先頭に位置しているために、第3版のアルゴリズムでも、ソート作業を早期に打ち切ることはできない。というのも、最大の要素9が、1回のパスで一つずつしか後ろに移動しないためである。
 そこで、奇数パスでは最小要素を先頭側に移動させ、偶数パスでは最大要素を末尾側に移動するというように、パスの走査方向を交互に変えると、このような並びを少ない比較回数でソートできる。バブルソートを改良したこのアルゴリズムは、双方向バブルソート(bidirection bubble sort)あるいはシェーカーソート(shaker sort)という名称で知られている。
 第3版を改良して、双方向バブルソートを行うプログラムを作成せよ。

// 演習6-5 // 双方向バブルソート(シェーカーソート) import java.util.Scanner; class ShakerSort {    //--- 配列の要素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 shakerSort(int[] a, int n) {       int left = 0;       int right = n - 1;       int last = right;       while (left < right){          for (int j = right; j > left; j--){             if (a[j - 1> a[j]){                swap(a, j - 1, j);                last = j;             }          }          left = last;          for (int j = left; j < right; j++){             if (a[j> a[j + 1]){                swap(a, j, j + 1);                last = j;             }          }          right = last;       }    }    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();       }       shakerSort(x, nx);            // 配列xを双方向バブルソート       System.out.println("昇順にソートしました。");       for (int i = 0; i < nx; i++)          System.out.println("x[" + i + "]=" + x[i]);    } }


戻る