明解 Javaによるアルゴリズムとデータ構造 6-6_クイックソート

6-6 クイックソート

クイックソートの概略

• クイックソート quick sort は、最も高速なアルゴリズムの一つ。
• C.A.R.Hoare が考案。
• 配列 a を枢軸 x pivot で分割することを繰り返す。

分割の手順

• a[pl] >= x が成立する要素が見つかるまで pl を右方向に走査
• a[pr] <= x が成立する要素が見つかるまで pr を左方向に走査
• 走査が共に止まったら、要素を入れ替える
• 配列は以下のように分類される
  • 枢軸以下のグループ　…　a[0], …, a[pl - 1]
  • 枢軸以上のグループ　…　a[pr + 1], …, a[n - 1]
  • pl > pr + 1 の時に限り、
    • 枢軸と一致するグループ　…　a[pr + 1], …, a[pl - 1]

クイックソート

• 分割を繰り返していくのがクイックソート
• 要素数が 1 になるまで分割を続ける。すなわち、
  • pr が先頭より右側に位置する (left < pr) のであれば(2つ以上の要素が存在するので)、左グループをさらに分割
  • pl が末尾より左側に位置する (pl < right) のであれば(2つ以上の要素が存在するので)、→グループをさらに分割
  • 中央グループが存在する場合、分割の対象から外れる(分割の必要が無いため)。
• 離れた 2 要素を交換するため、安定でない

ソースコード

• quickSort(int[] a, int left, int right) 版

import java.util.Scanner;

class QuickSort {
    static void swap(int[] a, int idx1, int idx2) {
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }

    static void quickSort(int[] a, int left, int right) {
        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);
        
        System.out.println("昇順にソートしました。");
        for (int i = 0; i < nx; i++) {
            System.out.println("x[" + i + "]: " + x[i]);
        }
    }
}

• quickSort(int[] a, int n) 版
  • 解答を見るに、現行メソッド活かして、オーバーロードで書いてねという趣旨らしい。先に言ってよ。

import java.util.Scanner;

class QuickSort2 {
    static void swap(int[] a, int idx1, int idx2) {
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }

    static void quickSort(int[] a, int n) {
        int pl = 0;
        int pr = n - 1;
        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 (0 < pr) {
            int[] b = new int[pr + 1];
            for (int i = 0; i < pr + 1; i++) {
                b[i] = a[i];
            }
            quickSort(b, pr + 1);
            for (int i = 0; i < pr + 1; i++) {
                a[i] = b[i];
            }
        }
        if (pl < n - 1) {
            int[] b = new int[n - pl];
            for (int i = 0; i < n - pl; i++) {
                b[i] = a[pl + i];
            }
            quickSort(b, n - pl);
            for (int i = 0; i < n - pl; i++) {
                a[pl + i] = b[i];
            }
        }
    }

    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, nx);
        
        System.out.println("昇順にソートしました。");
        for (int i = 0; i < nx; i++) {
            System.out.println("x[" + i + "]: " + x[i]);
        }
    }
}

• 実行結果

クイックソート
要素数: 9
x[0]: 44
x[1]: 88
x[2]: 77
x[3]: 55
x[4]: 66
x[5]: 99
x[6]: 22
x[7]: 11
x[8]: 33
昇順にソートしました。
x[0]: 11
x[1]: 22
x[2]: 33
x[3]: 44
x[4]: 55
x[5]: 66
x[6]: 77
x[7]: 88
x[8]: 99

非再帰的クイックソート

Stack 使って、配列の左端と右端を保持していればよい。

ソースコード

   static void quickSort(int[] a, int left, int right) {
        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[(pl + pr) / 2];

            System.out.printf("a[%d]~a[%d] : {", left, right);
            for (int i = left; i < right; i++) {
                System.out.printf("%d, ", a[i]);
            }
            System.out.printf("%d}\n", a[right]);

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

スタックの容量

• 分割後の要素数が少ない方から、分割を実施する方針を採る
  • スタックに積まれる数は、分割数に依存するから
  • 一般に、要素数の少ない配列のほうが、要素数の大きい配列よりも、分割 / ソートが簡単だから
• 積まれる総計が減少するわけではない。同時に積まれる数が減少するのみ。
• 配列の要素数 n であれば、スタックに積まれるデータ数は log n となる。

枢軸の選択

• 2分割は、同じ数に分かれるのが、最も効率がよい。1 : n-1 とかは最悪。
  • 枢軸の取り方が、効率に大きな影響を与える。

• 中央値がベストであるが、中央値算出にはそれなりのコストが必要。次善の策が求められる。

• 分割すべき配列の先頭要素/中央要素/末尾要素の3要素をソートし、さらに中央要素と末尾から2番目の要素を交換する。枢軸として、末尾から2番目の要素の値 a[right - 1] を採用し、分割の対象を a[left + 1] ～ a[right - 2] に絞り込む。

  • これだと、3要素での中央値算出と、中央要素と末尾から2番目の要素のスワップ1回を代償として、partition のための走査が pl + 1, pr - 2 から始められる。

時間計算量

• 一般には
  
  • パーティションでコスト n に加え、分割された小配列2つでのコストがそれぞれ・・・って再帰的に計算する
  • 某スレの17さんがわかりやすい

反映したコード

再帰版

import java.util.Scanner;

class QuickSort4 {
    static void swap(int[] a, int idx1, int idx2) {
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }

    static int getMed(int a, int b, int c) {
        if (a >= b) {
            if (b >= c) {
                return b;
            } else {
                return c;
            }
        } else {
            if (a >= c) {
                return a;
            } else {
                return b;
            }
        }
    }
    
    static void insertionSort(int[] a, int n) {
        for (int i = 1; i < n; i++) {
            int j;
            int tmp = a[i];
            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 + 1 <= 9) {
            insertionSort(a, right - left + 1);
        } else {
            int pl = left;
            int pr = right;

            int x;
            // 要素数3以上なら枢軸を工夫する
            if (pr - pl >= 2 ) {
                x = getMed(a[0], a[(pl + pr)/2], a[pr]);
            // 3未満なら工夫しない
            } else {
                x = a[(pl + pr) / 2];
            }
            
            System.out.printf("a[%d]~a[%d] : {" , left, right);
            for (int i = left; i < right; i++) {
                System.out.printf("%d, ", a[i]);
            }
            System.out.printf("%d}\n", a[right]);
            
            // 高速化のおまじない
            swap(a, (pl+pr)/2, pr+1);
            pr = pr -2;
            pl = pl +1;
            
            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);

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

非再帰版

import java.util.Scanner;


class QuickSortNotRecursive {
    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 n) {
        for (int i = 1; i < n; i++) {
            int j;
            int tmp = a[i];
            for (j = i; j > 0 && a[j - 1] > tmp; j--) {
                a[j] = a[j - 1];
            }
            a[j] = tmp;
        }
    }

    static int getMed(int a, int b, int c) {
        if (a >= b) {
            if (b >= c) {
                return b;
            } else {
                return c;
            }
        } else {
            if (a >= c) {
                return a;
            } else {
                return b;
            }
        }
    }
    
    static void quickSort(int[] a, int left, int right) {
        if (right - left + 1 <= 9) {
            insertionSort(a, right - left + 1);
        } 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;
                // 要素数3以上なら枢軸を工夫する
                if (pr - pl >= 2 ) {
                    x = getMed(a[0], a[(pl + pr)/2], a[pr]);
                // 3未満なら工夫しない
                } else {
                    x = a[(pl + pr) / 2];
                }

                System.out.printf("a[%d]~a[%d] : {", left, right);
                for (int i = left; i < right; i++) {
                    System.out.printf("%d, ", a[i]);
                }
                System.out.printf("%d}\n", a[right]);

                // 高速化のおまじない
                swap(a, (pl+pr)/2, pr+1);
                pr = pr -2;
                pl = pl +1;
                
                do {
                    while (a[pl] < x) {
                        pl++;
                    }
                    while (a[pr] > x) {
                        pr--;
                    }
                    if (pl <= pr) {
                        swap(a, pl++, pr--);
                    }
                } while (pl <= pr);

                if (pr - left > right - pl) {
                    if (left < pr) {
                        lstack.push(left);
                        rstack.push(pr);
                    }
                    if (pl < right) {
                        lstack.push(pl);
                        rstack.push(right);
                    }
                } else {
                    if (pl < right) {
                        lstack.push(pl);
                        rstack.push(right);
                    }
                    if (left < pr) {
                        lstack.push(left);
                        rstack.push(pr);
                    }
                }
            }
        }
    }

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

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

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