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

戻る  

演習6-12の解答

// 演習6-12
// クイックソート（先頭／中央／末尾要素をソートして中央値を枢軸とする）

import java.util.Scanner;

class QuickSortMed3Ex {

    //--- 配列の要素a[idx1]とa[idx2]を交換 ---//
    static void swap(int[] a, int idx1, int idx2) {
        int t = a[idx1];  a[idx1] = a[idx2];  a[idx2] = t;
    }

    //--- x[a], x[b], x[c]をソート（中央値のインデックスを返却）---//
    static int sort3Elem(int[] x, int a, int b, int c) {
        if (x[b] < x[a]) swap(x, b, a);
        if (x[c] < x[b]) swap(x, c, b);
        if (x[b] < x[a]) swap(x, b, a);
        return b;
    }

    //--- クイックソート（先頭／中央／末尾要素をソートして中央値を枢軸とする）---//
    static void quickSort(int[] a, int left, int right) {
        int pl = left;                // 左カーソル
        int pr = right;                // 右カーソル
        int x;                        // 枢軸
        if (pr - pl < 4)
            x = a[pl];
        else {
            int m = sort3Elem(a, pl, (pl + pr) / 2, pr);
            x = a[m];
            swap(a, m, right - 1);
            pl++;
            pr--;
        } 

        do {
            while (a[pl] < x) pl++;
            while (a[pr] > x) pr--;
            if (pl <= pr)
                swap(a, pl++, pr--);
        } while (pl <= pr);

        if (left < pr)  quickSort(a, left, pr);
        if (pl < right) quickSort(a, pl, right);
    }

    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();
        }

        quickSort(x, 0, nx - 1);                // 配列xをクイックソート

        System.out.println("昇順にソートしました。");
        for (int i = 0; i < nx; i++)
            System.out.println("x[" + i + "]＝" + x[i]);
    }
}

戻る