クイックソートの考え方は？

クイックソート登場

　バブルソートからはじめて、本質的には同じことをする2つのバージョンを作りました。プログラムというものは、どうしても技巧的になりますが、一方ではもっと直感的な方法をそのままプログラムにできるということを示しました。

　さて、今回は、技巧的なものの中でも恐らく一番というほど技巧的なものを紹介します。

　それはクイックソート（quicksort）と呼ばれるものです。このアルゴリズムを発見したのはH.A.R.ホーアという人です。コンピュータの基礎技術についてさまざまな研究をした人ですが、ホーアさん自身がこのアルゴリズムを発見したとき、そのあまりの速さに「quick」の名を付けたという有名な話が残っています。

　前置きはこれくらいにして、クイックソートを紹介しましょう。クイックソートにおける配列を並び替える方法の考え方は次のようなものです。

（1）与えられた配列を、1つの区切り目を境にして2つの区間に分ける、というのが基本的なアイデアです。
（2）このとき、左側の区間には「ある数値」よりも小さいものだけがあり、右側の区間にはその数値と等しいか大きいものだけがあるようにします。
（3）これを実現するために、左側にある「ある数値」よりも大きいものと、右側にある「ある数値」よりも小さいものを入れ替えます。これを左端、右端の両方から中央に向かって繰り返していき、中間で出会えば区間の分割が完了です。
（4）分割された2つの区間それぞれに対して、上の手順を繰り返し適用します。
（5）区間の要素数が1個になるまで繰り返します。

　言葉ではわかりにくいでしょうから、図1を見てください。

クイックソートの方法

　右端と左端に「視点」を置いています（1）。これを真ん中に向かって狭めていくのですが、その過程で上の（3）で説明した「入れ替え」をします。

　いま「ある数値」を5とします。この数値をどのように選ぶかでソート時間が大きく変わるのですが、いまは話を簡単にするために左端にある数値を使うことにします。それで5です（1）。

　さて、左端から見て行き、その数値が5より小さければ、左の「視点」を右に動かします。また、右端からも見て行き、その数値が5よりも大きければ右の「視点」を左に動かします。最終的に区間が区切られたとき、それぞれの区間にいる資格がある数値はそのまにしておいて良いので、その場合は視点を動かしていきます。

　図1の例では、左側は5で右側は2ですから、2つの視点はどちらも動きませんね。この時点で視点を動かすことはおしまいです。そこで2つの視点にある数値を入れ替えます（2）。同じように、視点を動かしながら入れ替えをしますが（3）、今のところはあくまで5と比較してこれを繰り返して、2つの視点が出会う（交差する）ところまで行きます（4）。ここではじめて2つの区間に分割されました（5）。

　これで左側には5よりも小さいものだけが集まっています。右側は5に等しいか5より大きいものだけになっています。

　さて、2つの区間に分かれましたが、続けてそれぞれの区間に対して同じことを繰り返します。