効率的なソートをするための一つの方法は分割です。データを分割してより小さな単位でソートし、あとであわせるという手法をつかって効率を上げています。
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の値と探す範囲と候補の番号を表示します。
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
dataの値を変化させても並べ替えがうまく行く事を確認します。(プログラムを変更したら再コンパイルする)
QSort02.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
データの順番を変更
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