Pythonでクイックソートを実装

標準的によく利用されているソート方法でありながら、その原理をきちんと理解するのはなかなか難しいクイックソート、そのアルゴリズムを解説します。

クイックソートのアルゴリズム

クイックソートは分割統治法の考え方で進められます。クイックソートの考え方を次図に示します。 

まず、ピボット（pivot）となる数値を決めます。これはどの要素でも構いません。ここでは、並べ替える配列の最後の要素としています。図では8をピボットとしています。

ピボットを決めたら、残りの要素を先頭と最後から中心に向かって調べていきます。両者を比較し、前者がピボット以上の値、後者がピボットより小さい値のときは、その値を交換します。前者がピボットより小さい値ときはそのまま後ろに進みます。後者がピボット以上の値のときもそのまま前に進みます。

探索が進み、両者がぶつかったところで全体の探索は終了です。このとき、探索がぶつかったところより先はピボットより小さい値ばかりとなっているはずで、後ろはピボット以上の値になっているはずだということはおわかりでしょう。これが理解できれば、前と後ろ、それぞれの集合をクイックソートの再帰呼び出しで処理すればよいということがわかります。

再帰の終端条件も簡単です。引数として与える配列の要素が1個ないしは空配列のときは、再帰呼び出しを行わずにそれのみからなる配列を返せばよいのです。図では最初のピボット以下の左側だけを図示していますが、全く同じ方法で右側も処理できます。

クイックソートの実装

Pythonによるクイックソートの実装例を次に示します。少し、複雑なプログラムになってしまいました。しかし、前述したクイックソートのアルゴリズムを理解していれば、このコードを理解するのはそれほど難しくはないでしょう。

def quick_sort(x):

  retary = []

  if len(x) > 1:

    y = x[:]; first = []; second = []

    pivot = y.pop()

    while len(y) > 0:

      top = y.pop(0)

      if top < pivot: first.append(top)

      else: second.insert(0, top)

      if len(y) == 0: break

      last = y.pop()

      if last < pivot: first.append(last)

      else: second.insert(0, last)

    retary = quick_sort(first) + [pivot] + quick_sort(second)

  else:

    retary.extend(x)

  return retary

さて、ソートの処理ですが、アルゴリズムの説明で示したように配列の添字を工夫して要素を入れ替えて、という処理は細かな条件判定がややこしくなりそうなので、配列を複製して先頭と末尾から要素を取り出しつつ進めていくという方針で実装しています。取り出した値を比較して、ピボットの左側（first）と右側（second）の配列に値を追加していくという方法で、先に示した交換方式と同じ結果となるようにしています。

y ＝ x[:]というコードは、スライスを用いて配列を複製するものです。その後、空の配列firstとsecondを用意し、複製したyの末尾からピボットを取り出しています。

while文は、複製したyが空になるまで繰り返します。先頭から取り出し、ピボットより小さければfirstに前から詰めていきます。ピボットより大きければsecondに後ろから詰めていきます。append()した結果が前から詰めることになる、あるいは、insert(0)した結果 が後ろから詰めることになるという処理に注意してください。

配列xが偶数個の要素を持つときは、複製したyからピボットを取り出した結果、yの要素数は奇数個になってしまいます。このとき、pop(0)としてtopを得た時点で配列yは空になってしまうので、そのときは繰り返し処理の途中で抜けなければいけません 。その対応が次のif文とbreak文の組み合わせです。

問題なければ後ろからlastを得て、同様にfirstまたはsecondに追加していきます。

繰り返しを終了した時点で配列firstにはpivotよりも小さい値のみが、配列secondにはpivot以上の値のみが詰められているはずです。したがって、再帰呼び出しでそれぞれをソートしたものを用意して、pivotを挟んでそれらを順番に並べてやれば 、全体がソートされているはず、という手順です。

上図にクイックソートの実行例を示します。配列xの内容が昇順に並べ替えられていることがわかるでしょう。