アルゴリズム図鑑 増補改訂版 絵で見てわかる33のアルゴリズム

 クイックソートは、「分割統治法」の一種です。元の問題を

2

つの子問題（ピボットよりも

小さいものと、ピボット以上のもの）に分割し、

2

つの子問題をそれぞれ解きます。それぞれ

の子問題がソート済みになったら、最 初 に説明したように、あとはそれらを単純にくっつけれ

ば（統治）、元の数列をソートした結果が得られます。

 なお、この子問題を解く部分にも、再 びクイックソートが使われます。さらにそのクイック

ソートの中でもクイックソートが使われます。子問題が

1

つの数字のみになったら、ソート済

みとして終了です。

 このように、アルゴリズムの内部にそのアルゴリズム自身を使うことを「再帰」といいま

す。再帰 については

7-4

節でも解説します。実は前節で見たマージソートも、再 帰 を使った分

割統治法とみなすことができます。



8-6

 

p.246



 子問題を作るためにピボットを選びますが、

2

つの子問題が元の問題の半分のサイズになる

ように毎回ピボットが選ばれていくと、クイックソートの計算時間はマージソートと同じく、

O

（

n

log

n

）になります。これはマージソートの場合と同様に、子問題のサイズが半分ずつに

なる過程を

log

2

n

回繰り返せば、要 素 が

1

つの子問題になり、ソート済みになるからです。し

たがって、ピボットにより数字を分割する様子を下図のように

1

段ずつ描いていくと、全 体 で

log

2

n

段になります。

5 7 63 421 98

5 7 63 421 98

pivot

5

7

6

3

4

2

1

9

8

5

7