新・明解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]);
   }
}

戻る