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

演習6-5の解答

　以下に示すデータの並びをソートすることを考えよう。
　　　　9 1 3 4 6 7 8
　ほぼソート済みであるにもかかわらず、最大の要素9が先頭に位置しているために、第3版のアルゴリズムでも、ソート作業を早期に打ち切ることはできない。というのも、最大の要素は、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]);
    }
}

戻る