クイックソート勉強

python

名前めっちゃ速そう！！

やり方を超大雑把にいうと、

  • 適当な数（ピボット）を選択して
  • ピボットより小さい数を前、大きい数を後ろに移動して分割
  • 分割されたパーティション内で再度ピボット選んで移動→分割を繰り返す

ということらしい。

arr = [30, 20, 60, 50, 90, 0, 40, 10, 70, 80]
def quick_sort(array, start, end):
  pivot = array[(end + start) / 2]
  i = start
  j = end
  while True:
    while array[i] < pivot: i += 1
    while pivot < array[j]: j -= 1
    if i >= j: break
    print i, j
    tmp = array[i]
    array[i] = array[j]
    array[j] = tmp

  if start < i - 1: my_quick(array, start, i - 1)
  if j + 1 < end: my_quick(array, j + 1, end)

if __name__ == '__main__':
  quick_sort(arr, 0, len(arr) - 1)
  print arr

MacBook% python sort.py
[0, 10, 20, 30, 40, 50, 60, 70, 80, 90]

おーできたー。

ただ、これだとデータが増えると再帰しすぎてスタックオーバーフローになるかも。
っていうかランダムなデータが10000個入った配列作って実行したら遅すぎて使いものにならなかった上に、たまに再帰しすぎ！みたいなエラーが出た。

ということは、フィボナッチ関数みたいに再帰は使わずに作った方がいいみたいですね。
再帰の代わりにスタックを使って書くのが普通みたいです。
ピボットで分割した小さいパーティションからスタックにプッシュ。

def quick_sort(array, start, end):
  l_stack = []
  r_stack = []
  l_stack.insert(0, start)
  r_stack.insert(0, end)
  sp = 1

  while sp > 0:
    sp -= 1
    left = l_stack[sp]
    right = r_stack[sp]

    if left < right:
      i = left
      j = right
      pivot = array[(left + right) / 2]
      while True:
        while array[i] < pivot: i += 1
        while pivot < array[j]: j -= 1
        if i >= j: break
        tmp = array[i]
        array[i] = array[j]
        array[j] = tmp

      if i - left < right - i:
        l_stack.insert(sp, i + 1)
        r_stack.insert(sp, right)
        sp += 1
        l_stack.insert(sp, left)
        r_stack.insert(sp, i - 1)
        sp += 1
      else:
        l_stack.insert(sp, left)
        r_stack.insert(sp, i - 1)
        sp += 1
        l_stack.insert(sp, i + 1)
        r_stack.insert(sp, right)
        sp += 1

ただ、この場合だとピボットの値が一番大きい数→2番目に大きい数→3番目...
となった場合に計算量がN ** 2となってしまうので、ピボットの選び方を改善する。

def quick_sort(array, start, end):
  # 省略
  pivot = select_pivot(array, i, j)
  # 省略

def select_pivot(array, i, j):
  a = array[i]
  b = array[(i + j) / 2]
  c = array[j]
  if a < b:
    if b < c: return b
    if a < c: return c
  elif a < c:
    return a
  elif b < c:
    return c
  return b

if __name__ == '__main__':
  my_quick(arr, 0, len(arr) - 1)
  print arr

すると、

MacBook% python sort.py
[0, 10, 20, 30, 40, 50, 60, 70, 80, 90]

とちゃんとソートできてる。
と、いいつつまだデータの並びによってはちょっと遅くなるな。。。
これは多分ピボットを3つしか選ぶようにしてないからその辺噛み合わない場合に遅くなるみたい。
まあwikipediaにもこのやり方が載っているし、とりあえずはよしとする。