クイックソート(QuickSort)

2019年11月24日ソート入門,ソート,クイックソート

クイックソートとは

クイックソートは分割統治法を用いたソートアルゴリズムの一種です。安定ではない内部ソートとなっています。マージソートの様に、再帰関数を用いることで配列を2分割してソートします。

マージソートは分割した配列を「マージ(併合)」しながらソートしますが、クイックソートは分割時にソートをしていきます。

最悪計算量は \(O(n^2)\) とマージソートの \(O(n \log n)\) より大きいですが、平均計算量は \(O(nlogn)\) です。また、マージソートはメモリを多く必要とする外部ソートですが、クイックソートは内部ソートなので、領域計算量は少なく済みます。

また、平均的には比較回数と交換回数が少なくて済むので、実用的で高速なアルゴリズムとしてよく用いられます。

アルゴリズム

まず「ピボット(pivot)」と呼ばれる要素を適当に選択します。その後「ピボットより小さい要素を左側・大きい要素を右側に移す」つまりピボットで配列を区切る(partition)ことを繰り返し、最終的にソートした配列を求めることができます。

  1. 何らかの方法で「ピボット」を配列の中から1つ選択する
  2. 「ピボット」より大きい数を右側、小さい数を左側に移動させる(partition)
  3. 左側と右側のそれぞれに対して、クイックソートを行う

「ピボット」を右側と左側のどちらに含めるかは実装にも依ります。左右どちらにも含めずに、中間にピボットが来るようにするアルゴリズムもあります。

partitionのアルゴリズム1

partitionのアルゴリズムはいくつか考えられます。一例として最も良く説明されているものを挙げると以下のようになります。

  1. ピボットを1つ選ぶ
  2. leftを配列の左端のindex, rightを右端のindexとする
  3. left<rightの間は以下を繰り返す
    1. left番目がピボット以上となるものが見つかるまで、leftを1増やすことを繰り返す
    2. right番目がピボットより小さいものが見つかるまで、rightを1減らすことを繰り返す
    3. left<rightならleft番目とright番目の要素を入れ替える

上のpartitionの方法では、ピボット以上のものは右側、ピボット未満のものは左側になります。このときピボット自身は右側に移ります。

もしもピボットが配列の中で最小で、他に同じ値の要素が存在しなければ無限ループとなります。分割(partition)をしても左側の領域の要素数は0です。そうなると、同じクイックソートを再帰的に呼び出し続けて終了しなくなってしまうのです。

partitionのアルゴリズム2

以下のようなアルゴリズムもあります。

  1. ピボットを1つ選ぶ
  2. \(i\)を配列の左端のindexとする
  3. \(j=i\)から配列の右端まで以下を繰り返し行う
    1. 配列の\(j\)番目がピボットより小さければ\(j\)番目と\(i\)番目の要素を入れ替える
    2. \(i\)を1増やす
  4. ピボットを中間に移動する（最後尾からピボットを選んだ場合は \(i\) 番目とピボットを入れ替えれば良い）

先程は左右から探索していましたが、このアルゴリズムは左側から最後まで探索していきます。このアルゴリズムでも同様に、最小の値をピボットに選択してしまうと無限ループに陥ってしまう可能性があります。（ただし、ピボットを中間に移動させるので、通常のピボットの選択方法から考えると、最小の値を連続でピボットに選択してしまうことはほとんど無いでしょう。）

無限ループを避けるための確実な方法

どちらのpartitionのアルゴリズムを利用しても、上手くピボットを選択しないと無限ループに陥る可能性があることが分かりました。

実はピボットを左右に含めずに中間に来るようにすると無限ループを防ぐことができます。ピボットを左右に含めないようにすれば、クイックソートの分割時に少なくとも1つずつは要素が減っていくので、最後には停止するのです。

2つ目のpartitionのアルゴリズムでは、ピボットを配列の右端から選ぶようにすれば、必ずピボットが中間に来るようになります。

ピボットの選択方法

ピボットの選択方法によっては、無限ループになってしまったり、計算時間が最悪に近づいてしまったりします。

例としてピボットの選択方法を挙げると以下のようなものがあります。

  • 配列の先頭を選ぶ
  • 配列の最後尾を選ぶ
  • 配列の中間の要素を選ぶ
  • ランダムに1つ選ぶ
  • ランダムに3つ選んで中央値を選ぶ
  • 前から見てはじめに得られた値の異なる2つの要素の大きい方を選ぶ

計算量

時間計算量(time complexity)

平均と最善の時の計算時間は \(O(nlogn)\)、最悪の時の計算時間は、\(O(n^2)\) です。

最悪時の計算量がいつ起こるか

ピボット選択が毎回配列の最小値か最大値の時に起こります。これは、partitionでの比較回数を合計すると、

$$(n-1) + (n-2) + … + 2 + 1 = \frac{n(n-1)}{2}$$

となるからです。

例えば、常に左端や右端の要素をピボットにするアルゴリズムでは、

  • すでに昇順にソートされている時
  • すでに降順にソートされている時

などに最悪(worst case)になります。これは良く生じる状態なので、別のピボット選択の方法を使ったほうが、最悪の計算量になりにくくなります。

領域計算量 (space complexity)

マージソートとは違い、配列のコピーは取らないので、\(O(1)\)のオーダーのメモリを消費します。なのでこれは内部ソートです。

プログラム例

まずは左右から探索するpartitionを用いたプログラムです。ピボットは右側に含めるとします。

Pythonでの例 (Colaboratory などで確認してみて下さい）

import random
def partition(arr, l, r): # 左右から探索して配列を分割
  pivot = random.choice(arr) # 配列からランダムにピボットを選ぶ
  left = l
  right = r
  while left < right:
    while(left<=r and arr[left] < pivot): # left<=r が無いとleftがrを超えて配列外の領域を参照する可能性があります
      left+=1
    while(l<=right and arr[right] >= pivot):　# l<=right が無いとrightがlを超えて配列外の領域を参照する可能性があります
      right-=1
    if(left<right):
      arr[left],arr[right] = arr[right],arr[left]
  return left # 右側(ピボット以上の領域)の先頭のindexを出力

def quick_sort(arr, l, r):
  if l<r:
    mid = partition(arr, l, r)
    quick_sort(arr, l, mid-1)
    quick_sort(arr, mid, r)

arr = [3,11,6,25,9,32,18]
quick_sort(arr,0,len(arr)-1)
print(arr)

次に、左から探索するpartitionを用いたプログラムです。ピボットは左右に含めず中間に持ってきます。

Pythonでの例 (Colaboratory などで確認してみて下さい）

def partition2(arr, l, r):
  pivot = arr[r] # 最後尾からピボットを選ぶ
  i = l
  for j in range(l,r):
    if arr[j] < pivot:
      arr[j], arr[i] = arr[i], arr[j]
      i +=1
  arr[i], arr[r] = arr[r], arr[i] # pivot を中間に移動
  return i # 中間にあるピボットのindexを出力
 
def quick_sort2(arr, l, r):
  if l<r:
    mid = partition2(arr, l, r)
    print(arr, mid)
    quick_sort2(arr, l, mid-1)
    quick_sort2(arr, mid+1, r) # mid番目の要素は中間にあるpivotなので使わない
 
arr = [3,11,6,25,9,32,18]
quick_sort2(arr,0,len(arr)-1)
print(arr)

ソート入門,ソート,クイックソート