【基本情報技術者試験】クイックソートをPythonで実装

今回はクイックソートをPythonで実装します。

1. 基本交換法（バブルソート）
2. 基本選択法（選択ソート）
3. 基本挿入法（挿入ソート）
4. シェルソート
5. クイックソート←今回の対象
6. マージソート
7. ヒープソート

クイックソートとは？

クイックソートとはある基準値を決めて、その基準値よりも値の小さなグループと大きなグループに分割することを繰り返すことでソートするアルゴリズムのことです。最も早いソートアルゴリズムの一つです。
例えば8, 3, 1, 2, 7, 5, 6, 4という数列があったときに下記のように更新していきます。

① 8, 3, 1, 2, 7, 5, 6, 4 （中央の数値2を基準とする）
② 2, 1, 3, 8, 7, 5, 6, 4 （左から２以上の数値(8)、右から２以下の数値(2)を入替、同様に3と1を入れ替える）
③ 2, 1, 3, 8, 7, 5, 6, 4 （前の手順で分割したグループそれぞれに対して更にソートを繰り返す）
④ 1, 2, 3, 8, 7, 5, 6, 4 （黄色のグループについて2を基準値としてソートすることで黄色のグループのソートは完了）
⑤ 1, 2, 3, 4, 6, 5, 7, 8 （基準値を7として、8と4、6と7を入れ替える）
⑥ 1, 2, 3, 4, 6, 5, 7, 8 （前の手順で分割してグループそれぞれに対してソートを行う）
⑦ 1, 2, 3, 4, 5, 6, 7, 8 （前の手順で分割してグループそれぞれに対してソートを行う）

実際のPythonのコードは下記になります。

def partition(listNum, start, end):
  # 基準値を中央の値にする
  pivot = listNum[(end - start + 1) // 2 - 1 + start]
  left = start
  right = end
  while 1:
    # 左から基準値以上の値を探索
    while listNum[left] < pivot:
      left += 1
    # 右から基準値以下の値を探索
    while pivot < listNum[right]:
      right -= 1
    if left >= right:
      return right + 1
    listNum[left], listNum[right] = listNum[right], listNum[left]
    left += 1
    right -= 1
    print(listNum)

def quicksort(listNum, start, end):

  # 基準値によって分割された左右のグループそれぞれに対してクイックソートを行う
  if start < end:
    p = partition(listNum, start, end)
    quicksort(listNum, start, p - 1)
    quicksort(listNum, p, end)

listNum = [8, 3, 1, 2, 7, 5, 6, 4]
listNum

[8, 3, 1, 2, 7, 5, 6, 4]

quicksort(listNum, 0, 7)

[2, 3, 1, 8, 7, 5, 6, 4]
[2, 1, 3, 8, 7, 5, 6, 4]
[1, 2, 3, 8, 7, 5, 6, 4]
[1, 2, 3, 4, 7, 5, 6, 8]
[1, 2, 3, 4, 6, 5, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]

クイックソートについては以上となります。
次回はマージソートについて扱います。