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

戻る  

演習6-15の解答

// 演習6-15
// クイックソート（分割すべき配列の要素数が9以下であれば単純挿入ソートに切替え）

import java.util.Scanner;

class QuickInsertSort {

    //--- 配列の要素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 insertionSort(int[] a, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int tmp = a[i];
            int j;
            for (j = i; j > 0 && a[j - 1] > tmp; j--)
                a[j] = a[j - 1];
            a[j] = tmp;
        }
    }

    //--- 配列を分割する ---//
    static void quickSort(int[] a, int left, int right) {
        if (right - left <= 9)
            insertionSort(a, left, right);
        else {
            int    pl = left;                // 左カーソル
            int    pr = right;                // 右カーソル
            int    x = a[(pl + pr) / 2];    // 枢軸（中央の要素）
    
            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]);
    }
}

// 演習6-15
// クイックソート（非再帰版：分割すべき配列の要素数が9以下であれば単純挿入ソートに切替え）

import java.util.Scanner;

class QuickInsertSort2 {

    //--- 配列の要素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 insertionSort(int[] a, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int tmp = a[i];
            int j;
            for (j = i; j > 0 && a[j - 1] > tmp; j--)
                a[j] = a[j - 1];
            a[j] = tmp;
        }
    }

    //--- クイックソート（非再帰版）---//
    static void quickSort(int[] a, int left, int right) {
        if (right - left <= 9)
            insertionSort(a, left, right);
        else {
            IntStack lstack = new IntStack(right-left+1);
            IntStack rstack = new IntStack(right-left+1);
    
            lstack.push(left);
            rstack.push(right);
    
            while (lstack.isEmpty() != true) {
                int    pl = left  = lstack.pop();        // 左カーソル
                int    pr = right = rstack.pop();        // 右カーソル
                int    x = a[(left + right) / 2];        // 枢軸は中央の要素
    
                do {
                    while (a[pl] < x) pl++;
                    while (a[pr] > x) pr--;
                    if (pl <= pr)
                        swap(a, pl++, pr--);
                } while (pl <= pr);
    
                if (left < pr) {
                    lstack.push(left);            // 先頭側グループの範囲
                    rstack.push(pr);            // （インデックス）をプッシュ
                }
                if (pl < right) {
                    lstack.push(pl);            // 末尾側グループの範囲
                    rstack.push(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]);
    }
}

戻る