クイックソートによる並べかえ

整列法3. クイックソートによる並べかえ

効率的なソートをするための一つの方法は分割です。データを分割してより小さな単位でソートし、あとであわせるという手法をつかって効率を上げています。

ファイル名 QSort01.java

public class QSort01 {
    public static void main( String[] args ) {
        int[] data = { 44, 86, 24, 57, 78, 65, 39 };
                     // 0,  1,  2,  3,  4,  5,  6
        qksort(data,0,data.length-1);
        for ( int i=0; data.length>i; i++) {
            System.out.print( data[i]+" " );
        }
        System.out.println();
    }//mainの終わり

    static void qksort(int a[],int kokokara,int kokomade){
        int small = kokokara;
        int large = kokomade;
        int mid   = (small+large)/2;
        int kijun = a[mid];        //これが基準値. midの値は気にしない!!
        while(true){
            while (  kokomade>small && kijun > a[small] ) small++; //左から大きいものを検索
            while ( large>kokokara && a[large] > kijun ) large--; //右から小さいものを検索
            if ( small > large ) break;         //無限ループから抜ける
            if ( small != large ){
                int tmp  = a[small]; 
                a[small] = a[large];
                a[large] = tmp;
            }
            small++;
            large--;
        }
        if (large > kokokara) qksort(a,kokokara,large); //前半を指定して再帰呼び出し
        if (kokomade > small) qksort(a,small,kokomade); //後半を指定して再帰呼び出し
　　}//qksortの終わり
}//classの終わり

コンパイルと実行は次のようにします。

$ javac QSort01.java 
$ java QSort01 
24 39 44 57 65 78 86 

途中経過を表示する

交換する候補が見つかるたびに、dataの値と探す範囲と候補の番号を表示します。

ファイル名 QSort02.java

public class QSort02 {
    public static void main( String[] args ) {
        int[] data = { 44, 86, 24, 57, 78, 65, 39 };
                     // 0,  1,  2,  3,  4,  5,  6
        qksort(data,0,data.length-1);
        for ( int i=0; data.length>i; i++) {
            System.out.print( data[i]+" " );
        }
        System.out.println();
    }//mainの終わり

    static void qksort(int a[],int kokokara,int kokomade){
        int small = kokokara;
        int large = kokomade;
        int mid   = (small+large)/2;
        int kijun = a[mid];        //これが基準値. midの値は気にしない!!
        while(true){
            while (  kokomade>small && kijun > a[small] ) small++; //左から大きいものを検索
            while ( large>kokokara && a[large] > kijun ) large--; //右から小さいものを検索
            print(a,kijun,kokokara,small,large,kokomade);
            if ( small > large ) break;         //無限ループから抜ける
            if ( small != large ){
                int tmp  = a[small]; 
                a[small] = a[large];
                a[large] = tmp;
            }
            small++;
            large--;
        }
        if (large > kokokara) qksort(a,kokokara,large); //前半を指定して再帰呼び出し
        if (kokomade > small) qksort(a,small,kokomade); //後半を指定して再帰呼び出し
    }//qksortの終わり
    static void print(int[] data, int kijun, int b, int s,int l, int e){
        for (int x = 0; data.length>x; x++) {
            System.out.printf("%4d",data[x]);
        } 
        System.out.printf(": kijun=%3d kara=%2d sm=%2d lg=%2d made=%2d",kijun,b,s,l,e );
        System.out.println();
        return;
    }//printの終わり
}//classの終わり

コンパイルと実行は次のようにします。

色をつけたところは、今回の範囲とその中の交換候補です。

$ javac QSort02.java 
$ java QSort02
  44  86  24  57  78  65  39: kijun= 57 kara= 0 sm= 1 lg= 6 made= 6
  44  39  24  57  78  65  86: kijun= 57 kara= 0 sm= 3 lg= 3 made= 6
  44  39  24  57  78  65  86: kijun= 57 kara= 0 sm= 4 lg= 2 made= 6
  44  39  24  57  78  65  86: kijun= 39 kara= 0 sm= 0 lg= 2 made= 2
  24  39  44  57  78  65  86: kijun= 39 kara= 0 sm= 1 lg= 1 made= 2
  24  39  44  57  78  65  86: kijun= 39 kara= 0 sm= 2 lg= 0 made= 2
  24  39  44  57  78  65  86: kijun= 65 kara= 4 sm= 4 lg= 5 made= 6
  24  39  44  57  65  78  86: kijun= 65 kara= 4 sm= 5 lg= 4 made= 6
  24  39  44  57  65  78  86: kijun= 78 kara= 5 sm= 5 lg= 5 made= 6
  24  39  44  57  65  78  86: kijun= 78 kara= 5 sm= 6 lg= 4 made= 6
24 39 44 57 65 78 86 

並べかえ前のデータの順番を変えてみる(1)

dataの値を変化させても並べ替えがうまく行く事を確認します。(プログラムを変更したら再コンパイルする)

QSort02.java をもとに書き換えて QSort03.java を作ります。

ファイル名 QSort03.java の変更点

データの順番を変更

        int[] data = { 44, 24, 57, 86, 78, 65, 39 };

コンパイルと実行は次のようにします。

$ javac QSort03.java 
$ java QSort03
  44  24  57  86  78  65  39: kijun= 86 kara= 0 sm= 3 lg= 6 made= 6
  44  24  57  39  78  65  86: kijun= 86 kara= 0 sm= 6 lg= 5 made= 6
  44  24  57  39  78  65  86: kijun= 57 kara= 0 sm= 2 lg= 3 made= 5
  44  24  39  57  78  65  86: kijun= 57 kara= 0 sm= 3 lg= 2 made= 5
  44  24  39  57  78  65  86: kijun= 24 kara= 0 sm= 0 lg= 1 made= 2
  24  44  39  57  78  65  86: kijun= 24 kara= 0 sm= 1 lg= 0 made= 2
  24  44  39  57  78  65  86: kijun= 44 kara= 1 sm= 1 lg= 2 made= 2
  24  39  44  57  78  65  86: kijun= 44 kara= 1 sm= 2 lg= 1 made= 2
  24  39  44  57  78  65  86: kijun= 78 kara= 3 sm= 4 lg= 5 made= 5
  24  39  44  57  65  78  86: kijun= 78 kara= 3 sm= 5 lg= 4 made= 5
  24  39  44  57  65  78  86: kijun= 57 kara= 3 sm= 3 lg= 3 made= 4
  24  39  44  57  65  78  86: kijun= 57 kara= 3 sm= 4 lg= 2 made= 4
24 39 44 57 65 78 86 

並べかえ前のデータの順番を変えてみる(2)

ファイル名 QSort04.java の変更点

データの順番を変更

        int[] data = {  44, 57, 86, 65, 24, 78, 39 };

コンパイルと実行は次のようにします。

$ javac QSort04.java 
$ java QSort04
  44  57  86  65  24  78  39: kijun= 65 kara= 0 sm= 2 lg= 6 made= 6
  44  57  39  65  24  78  86: kijun= 65 kara= 0 sm= 3 lg= 4 made= 6
  44  57  39  24  65  78  86: kijun= 65 kara= 0 sm= 4 lg= 3 made= 6
  44  57  39  24  65  78  86: kijun= 57 kara= 0 sm= 1 lg= 3 made= 3
  44  24  39  57  65  78  86: kijun= 57 kara= 0 sm= 3 lg= 2 made= 3
  44  24  39  57  65  78  86: kijun= 24 kara= 0 sm= 0 lg= 1 made= 2
  24  44  39  57  65  78  86: kijun= 24 kara= 0 sm= 1 lg= 0 made= 2
  24  44  39  57  65  78  86: kijun= 44 kara= 1 sm= 1 lg= 2 made= 2
  24  39  44  57  65  78  86: kijun= 44 kara= 1 sm= 2 lg= 1 made= 2
  24  39  44  57  65  78  86: kijun= 78 kara= 4 sm= 5 lg= 5 made= 6
  24  39  44  57  65  78  86: kijun= 78 kara= 4 sm= 6 lg= 4 made= 6
24 39 44 57 65 78 86