１ データのブロック分割 ２ 各ブロックごとの処理（並べ換え） ３ ブロックの統合であり、クイックソートでは特に１のデータの分割にアルゴリズムのよさの秘密が隠されている。例を用いてクイックソートのアルゴリズムを解説しよう。
48 65 10 36 83 5 21 72ステップ０１
48 65 10 36 83 5 21 72
ステップ０２
21 65 10 36 83 5 48 72
さらに、ステップ０２を続けると、５と６５が入れ替わる。
21 5 10 36 83 65 48 72
以下、同様な操作を繰り返し、注目している点が交差するまで行なう。すると
21 5 10 36 83 65 48 72
が得られる。これは、基準値とした位置（左から４番目）を境に、左右ブロックに分割したことになる。左側には４番目のデータ（３６）よりも小さいデータ、右側には大きいデータとなる。
ステップ１ー１
左側のブロックに対して、ステップ０１、０２を行なう。
21 5 10 5 ｜ 21 10よって、５と２１，１０とに分割できる。
ステップ１ー１ー１
さらに、左側についてステップ０１、０２を行なう。この場合、５だけなのでなにもしない。
ステップ１ー１ー２
右側の２１，１０についてステップ０１、０２を行なう。
上記ステップ１ー１ー１、１ー１ー２により、
５ １０ ２１
が得られる。
ステップ１ー２
８３，６５，４８，７２について同様にステップ０１、０２を行なう。よって、
5 10 21 36 48 65 72 83
が得られる。
基準点としたデータが、左、右いずれかのブロックに含まれる時と含まれない時がある。その詳細についてはプログラム６−４を見ていただきたい。ここでは、アルゴリズムの大体の考え方を理解できればよいと考えている。
クイックソートのプログラムは以下のようである。
1: void QuickSort( int data[], int upper, int lower ) {
2: int mid, tmp, i, j;
3:
4: i = upper;
5: j = lower;
6: mid = data[(lower+upper)/2];
7: do {
8: while( data[i] < mid ) i++;
9: while( mid < data[j] ) j--;
10: if( i <= j ) {
11: tmp = data[i];
12: data[i] = data[j];
13: data[j] = tmp;
14: i++;
15: j--;
16: }
17: } while( i <= j );
18: if ( upper < j ) QuickSort(data, upper, j);
19: if ( i < lower ) QuickSort(data, i, lower);
20: }
Quicksortメソッドは、プログラム内部でさらに自分自身を呼んでいる。つまり再帰的なアルゴリズムとなっている。先に示した例のデータを用いて実行の様子を表現すると、下記のような構造となっている。
( 48 65 10 36 83 5 21 72 )
｜
｜QuickSort(1,8)
−−−−− ＋−−−−−−−
｜ ｜ ｜
( 21 5 10 ) ( 36 ) ( 83 65 48 72 )
｜ ｜
QuickSort(1,3)｜ ｜QuickSort(5,8)
−−− ＋−− −−＋−−−−
｜ ｜ ｜ ｜
( 5 ) ( 21 10 ) ( 48 ) ( 65 ) ( 83 72 )
｜ ｜
QuickSort(2,3)｜ ｜QuickSort(7,8)
−−＋−− −−＋−−
｜ ｜ ｜ ｜
( 10 ) ( 21 ) ( 72 ) ( 83 )
よって分割したブロックを統合すると、
5 10 21 36 48 65 72 83となる。
クイックソートの計算時間量を評価してみよう。今回は、プログラム中の１１〜１３の実行回数をカウントすることで、オーダーを求めることにする。
１段目 QuickSort(1,n)では、入れ替えの起こる確率を１／２とすると約ｎ／２回
実行される。
２段目 QuickSort(1,n/2)、QuickSort(n/2,n)では、入れ替えの起こる確率を１／２と
するとそれぞれ約ｎ／４回実行される。二つの回数を合わせると、約ｎ／２回
の実行となる。
３段目 ４つの関数QuickSort(1,n/4)、QuickSort(n/4,n/2)、QuickSort(n/2,3n/4)、
QuickSort(3n/4,n)が実行されそれぞれ約ｎ／８回の実行となる。これらを合
わせると約ｎ／２回の実行となる。
４段目 同様に考えると８回のQuickSort関数を実行し、それぞれ約ｎ／１６回実行。
合わせると約ｎ／２回の実行回数となる。
以上から、各段階では約ｎ／２回の入れ替えが起こることがわかる。