public class Quick01 {
public static void main( String[] args ) {
int[] data = { 52, 46, 24, 12, 35, 15, 18, 56, 63, 23 };
int imax = data.length-1;
print(a,kijun,0,imax);
qksort(data,0,imax);
for ( int i=0; imax>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,small,large);
if ( small > large ) break; //無限ループから抜ける
int tmp = a[small];
a[small] = a[large];
a[large] = tmp;
print(a,kijun,small,large);
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 i, int j){
for (int x = 0; data.length>x; x++) {
System.out.printf("%4d",data[x]);
}
System.out.printf(": kijun=%3d small=%2d large=%2d",kijun,i,j );
System.out.println();
return;
}//printの終わり
}//classの終わり
実行結果は
$ javac Quick01.java $ java Quick01 52 46 24 12 35 15 18 56 63 23: kijun= 0 small= 0 large= 9 52 46 24 12 35 15 18 56 63 23: kijun= 35 small= 0 large= 9 23 46 24 12 35 15 18 56 63 52: kijun= 35 small= 0 large= 9 23 46 24 12 35 15 18 56 63 52: kijun= 35 small= 1 large= 6 23 18 24 12 35 15 46 56 63 52: kijun= 35 small= 1 large= 6 23 18 24 12 35 15 46 56 63 52: kijun= 35 small= 4 large= 5 23 18 24 12 15 35 46 56 63 52: kijun= 35 small= 4 large= 5 23 18 24 12 15 35 46 56 63 52: kijun= 35 small= 5 large= 4 23 18 24 12 15 35 46 56 63 52: kijun= 24 small= 2 large= 4 23 18 15 12 24 35 46 56 63 52: kijun= 24 small= 2 large= 4 23 18 15 12 24 35 46 56 63 52: kijun= 24 small= 4 large= 3 23 18 15 12 24 35 46 56 63 52: kijun= 18 small= 0 large= 3 12 18 15 23 24 35 46 56 63 52: kijun= 18 small= 0 large= 3 12 18 15 23 24 35 46 56 63 52: kijun= 18 small= 1 large= 2 12 15 18 23 24 35 46 56 63 52: kijun= 18 small= 1 large= 2 12 15 18 23 24 35 46 56 63 52: kijun= 18 small= 2 large= 1 12 15 18 23 24 35 46 56 63 52: kijun= 12 small= 0 large= 0 12 15 18 23 24 35 46 56 63 52: kijun= 12 small= 0 large= 0 12 15 18 23 24 35 46 56 63 52: kijun= 12 small= 1 large=-1 12 15 18 23 24 35 46 56 63 52: kijun= 18 small= 2 large= 2 12 15 18 23 24 35 46 56 63 52: kijun= 18 small= 2 large= 2 12 15 18 23 24 35 46 56 63 52: kijun= 18 small= 3 large= 1 12 15 18 23 24 35 46 56 63 52: kijun= 56 small= 7 large= 9 12 15 18 23 24 35 46 52 63 56: kijun= 56 small= 7 large= 9 12 15 18 23 24 35 46 52 63 56: kijun= 56 small= 8 large= 7 12 15 18 23 24 35 46 52 63 56: kijun= 46 small= 6 large= 6 12 15 18 23 24 35 46 52 63 56: kijun= 46 small= 6 large= 6 12 15 18 23 24 35 46 52 63 56: kijun= 46 small= 7 large= 5 12 15 18 23 24 35 46 52 63 56: kijun= 63 small= 8 large= 9 12 15 18 23 24 35 46 52 56 63: kijun= 63 small= 8 large= 9 12 15 18 23 24 35 46 52 56 63: kijun= 63 small= 9 large= 8 12 15 18 23 24 35 46 52 56
効率的なソートをするための一つの方法は分割です。データを分割してより小さな単位でソートし、あとであわせるという手法をつかって効率を上げています。つまり、
１ データのブロック分割
２ 各ブロックごとの処理（並べ換え）
３ ブロックの統合
という順に作業がすすめられるわけです。速くなるかどうかは１のデータの分割の仕方が工夫のしどころでいろいろなやり方が提案されています。ここで取り上げるのはその中の１つです。。
実際にやってみます。
(１)最初の行はまだ qksort を呼び出す前の、print(a,kijun,0,imax); によって表示されます。初期状態です。
52 46 24 12 35 15 18 56 63 23: kijun= 0 small= 0 large= 9
(２)まず与えられたデータ列の真ん中に位置する データを基準値として定めます。例では、左から5番目の 35 が基準値となりました。次に、データを左から順に基準値よりも大きいデータを捜します。まず52が見つかります。続いて、右から順に基準値よりも小さいデータを捜します。 23が見つかります。
52 46 24 12 35 15 18 56 63 23: kijun= 35 small= 0 large= 9
(３)ここで、52と23を入れ替えます。現在注目しているデータの位置を次に進めます（左から見ている場合は一つ右へ、右からの場合は左へ一つ進める）。
23 46 24 12 35 15 18 56 63 52: kijun= 35 small= 0 large= 9
(４)引き続き左から順に基準値よりも大きいデータを捜します。続きは46から始まりますかすぐ46が見つかります。続いて、右から順に基準値よりも小さいデータを捜します。 18が見つかります。
23 46 24 12 35 15 18 56 63 52: kijun= 35 small= 1 large= 6
(５)46と18を交換します。
23 18 24 12 35 15 46 56 63 52: kijun= 35 small= 1 large= 6
(６)続けて左から基準値より大きいデータを探します。基準値に等しい場合も取り上げることにすると35そのものに合います。右からも同様に小さいものを探すと15が見つかります。
23 18 24 12 35 15 46 56 63 52: kijun= 35 small= 4 large= 5
(7)35と15を交換します。
23 18 24 12 15 35 46 56 63 52: kijun= 35 small= 4 large= 5
(8)i の方が大きくなってしまいました。large(4)より左は基準値より小さなものが、small(5)より右は大きいものが集まっています。breakすると、２つの部分に分けて、それぞれ（１）からと同様に作業をしていきます。まずは0からlargeまで。
23 18 24 12 15 35 46 56 63 52: kijun= 35 small= 5 large= 4
(9)前半分は１番から５番までです。データ列の真ん中（左から３番目）に位置するデータを基準値として定めます。例では、２４になります。以下同様なのですが、今回は基準値が、たまたまその範囲の最高値になっているのでちょっと面倒です。こんなときでもうまくいきます。
23 18 24 12 15 35 46 56 63 52: kijun= 24 small= 2 large= 4
(10)２４と１５を交換します。
23 18 15 12 24 35 46 56 63 52: kijun= 24 small= 2 large= 4
(11)続けて左側から基準値より大きいものを探します。さっきは２４が３番にありました。今度は４番から探します。すると５番の２４が見つかります。右側からは、基準値より小さいものを探します。さっきは５番に１５がありましたから今度は４番から始めます。すぐ１２が小さいということになります。
23 18 15 12 24 35 46 56 63 52: kijun= 24 small= 4 large= 3
(12)これで左右からの捜索がぶつかりました。左から来たのは５番の２４まで来ましたし、右からのは４番の１２まできましたから、交差して行き過ぎています。このようなときは交換せず、４番と５番の間でデータを２つに分けます。基準値であった２４よりも小さいものと大きいものに分かれます。右側の２４より大きいのは１つしかありませんが、たまたまこの範囲の最大値だったので仕方ありません。一つしかない要素はこのまま位置が確定します。
23 18 15 12 24 35 46 56 63 52: kijun= 18 small= 0 large= 3
(12)分かれた１番から４番に対してふたたび(１)からのように、作業をします。繰り返すうち、要素が１つ部分ができては確定してゆきます。前半が終われば後半に進み、ついには全部整列されます。
ある基準値を決めて、それより大きいか小さいかで２つに分け、分かれたものについても同じことを繰り返す。ということです。基準値はデータの大きさで真ん中あたりの数であれば都合がいいのですが、それをじっくり選んでいると時間がかかるので位置で真ん中のものを「えいっ」とつかんで採用するわけです。
原理的にはここまでなのですが、実際にプログラムを組むときには分けるときの境界を含めるか含めないかで迷います。>= を使うか、> を使うかを間違えると、うまく働かないこともありますから、じっくり考えなければならないことになります。
12 18 15 23 24 35 46 56 63 52: kijun= 18 small= 0 large= 3
12 18 15 23 24 35 46 56 63 52: kijun= 18 small= 1 large= 2
12 15 18 23 24 35 46 56 63 52: kijun= 18 small= 1 large= 2
12 15 18 23 24 35 46 56 63 52: kijun= 18 small= 2 large= 1
12 15 18 23 24 35 46 56 63 52: kijun= 12 small= 0 large= 0
12 15 18 23 24 35 46 56 63 52: kijun= 12 small= 0 large= 0
12 15 18 23 24 35 46 56 63 52: kijun= 12 small= 1 large=-1
12 15 18 23 24 35 46 56 63 52: kijun= 18 small= 2 large= 2
12 15 18 23 24 35 46 56 63 52: kijun= 18 small= 2 large= 2
12 15 18 23 24 35 46 56 63 52: kijun= 18 small= 3 large= 1
12 15 18 23 24 35 46 56 63 52: kijun= 56 small= 7 large= 9
12 15 18 23 24 35 46 52 63 56: kijun= 56 small= 7 large= 9
12 15 18 23 24 35 46 52 63 56: kijun= 56 small= 8 large= 7
12 15 18 23 24 35 46 52 63 56: kijun= 46 small= 6 large= 6
12 15 18 23 24 35 46 52 63 56: kijun= 46 small= 6 large= 6
12 15 18 23 24 35 46 52 63 56: kijun= 46 small= 7 large= 5
12 15 18 23 24 35 46 52 63 56: kijun= 63 small= 8 large= 9
12 15 18 23 24 35 46 52 56 63: kijun= 63 small= 8 large= 9
12 15 18 23 24 35 46 52 56 63: kijun= 63 small= 9 large= 8