クイックソート                                  戻る

 例えば、10個の数があって、それらを大きさの順に並べ替える(この操作を、ソート(sort)
という)ことを考える。この問題に対して、多くの人は次のように考えるだろう。

 1つの数Aを選んで、残りの数Bと大小を比較する。A≦Bなら、Aはそのまま、A>Bなら、
Bを新たにAとする。この手順を繰り返して最小値を求める。次に、この最小値を除いた残り
について、同じ操作を行い、順次第2最小値、第3最小値、・・・を決めていく。

 しかし、この方法だと、最大44回の大小比較が必要である。

 このことについて、次のようなクイックソート(quick sort)という方法が知られている。

 n個の異なった数 X、X、X、・・・、X について、
(1) n=2 のとき、2つの数の大小を比較する。
(2) n>2 のとき、まず、n個のうちどれか一つAを任意に選択する。
            残りのn−1個を、Aと比較して、n−1個の数を
             S:Aより小さい数からなる集合
             L:Aより大きい数からなる集合
            という2つの集合に分類する。
  この、SとLについて、上記(1)(2)の操作を行い、以下順次繰り返す。

例 10、3、7、6、13、1、9、4、8、11 について、クイックソートを行ってみよう。
      10、3、7、6、13、1、9、4、8、11
   適当な数、例えば、9を選んで、2つの集合に分類する。
      3、7、6、1、4、8  9  10、13、11         (大小比較の回数 9回)
   適当な数、例えば、6を選んで、2つの集合に分類する。
      3、1、4  6  7、8  9  10、13、11       (大小比較の回数 5回)
   適当な数、例えば、3を選んで、2つの集合に分類する。
      1  3  4  6  7、8  9  10、13、11     (大小比較の回数 2回)
   適当な数、例えば、7を選んで、2つの集合に分類する。
      1  3  4  6  7  8  9  10、13、11    (大小比較の回数 1回)
   適当な数、例えば、11を選んで、2つの集合に分類する。
      1  3  4  6  7  8  9  10  11  13  (大小比較の回数 2回)
以上で並べ替えは終了である。この場合の大小比較の回数は全部で19回である。
もちろん、Aの選び方によって大小比較の回数は変化するが、並べ替えの方法としては、
だいぶ改善されている筈である。


(参考文献:玉置光司 著 基本確率(牧野書店))