クイックソートの詳細とコード事例

クイックソートとは？

要素をピボット（基準）を決めて、残りの要素を、ピボットより大きいいか、小さいかで前後に配置していく。

この前後に配置した要素を更に、ピボットを決め前後に配置していく作業を繰り返す。

要素が１つになったら確定する。

▼先頭の要素をpivotにする場合

クイックソートの流れ

1. ピボットを決定し、その数値より大きいか小さいかで前後に振り分けていく。ピボットの値と場所は確定とする。
2. 前方の配列に対し、再度１の処理を行う
3. 後方の配列に対し、再度１の処理を行う
4. ２、３の処理でピボットがどんどん確定していき、最終的には全ての要素が確定する。

一番左側をpivotにした場合

##pivotを指定して左側＋pivot+右側で並び替えた配列を作る関数（quick_sort）
def quick_sort(arr):
  #要素が１つになったらソート終了（要素が２つ未満の場合はソート不要）
  if len(arr) <= 1 :
    return arr
  #pivotの値を指定
  p = arr[0]

  #pivotを基準に分割する処理を行う。div関数
  arr1, arr2 = div(p, arr[1:])

  #pivotを基準にして、分割した配列を結合する。
  #分割した配列自体にもquick_sortを行う。
  return quick_sort(arr1) + [p] + quick_sort(arr2)



##pivotを基準に左側と右側の配列を作成する関数 (div)
def div(p, arr):
  #pivotの左側と右側の配列を入れる変数を定義
  left, right=[], []

  for i in arr:
    #pivotより小さければ左側に格納
    if i < p:
      left.append(i)
    #pivot以上であれば右側に格納
    else:
      right.append(i)

  #左側と右側の配列をそれぞれ出力
  return left, right

マージソートに比べると直感的でわかりやすい。

※注意
一番左側の値をpivotにすると、既に降順に並んでいる場合などに計算量が多くなってしまう。

このため、pivotはランダムに決定することが推奨される。

pivotをランダムに決定した場合のクイックソート

numpyのrandom.choice(配列)を使用する。

上記のquick_sort関数のpivotを以下のように変更する。

import numpy as np
  p = random.choice(arr)

quick_sort

import numpy as np

def quick_sort2(arr):
  #要素が１つになったらソート終了（要素が２つ未満の場合はソート不要）
  if len(arr) <= 1 :
    return arr

  #pivotの値を指定
  p = random.choice(arr)

  #pivotを基準に分割する処理を行う。div関数
  arr1, arr2 = div(p, arr[1:])

  #pivotを基準にして、分割した配列を結合する。
  #分割した配列自体にもquick_sortを行う。
  return quick_sort(arr1) + [p] + quick_sort(arr2)