@suzu6

主にWEBと解析の技術について書きます。

広く浅くも続ければ深くなるはず。

クイックソートのコード | Python

Python3でクイックソートをするコードです。

クイックソート

クイックソートは分割統治アルゴリズムの一種です。

bunkasu

分割統治アルゴリズムは上図のように、配列を分割して細かくしながら問題を解決していく手法です。 この種のアルゴリズムの計算量はO(nlogn)O(n \log n)です。

クイックソートでは、要素から基準値(ピボット)を選びそれと比較して小さい要素を左大き要素を右へ交換して問題を小さく分割していきます。 (降順では左右を反対にする)

今回実装した手順は、以下の4つです。

  1. 走査する配列長が0か1の場合戻る。
  2. 走査する範囲の中央の要素をピボットとして選ぶ。
  3. ピボットと比べ、大きい要素は左へ小さい要素は右へ交換する。
  4. 左右2つに配列を分割してこの関数を再帰的に繰り返す。

2のピボットを選ぶ基準は中央の要素でなくても良い。

ソートのアニメーション

quick-sort

後半のソートが一瞬ですね。

アニメーションは以下の記事で作成しました。

コード

4.で左右に配列を分割する際、基準にしたピボットは含まないようにしています。

import math
import random # ランダムな配列の生成用


def quick_sort(arr):
    """ クイックソート 
    """
    if len(arr) < 2:
        # 1. 走査する配列長が0か1の場合戻る。
        print(arr)
        return arr

    # 2. 走査する範囲の中央の要素をピボットとして選ぶ。
    pivot = math.floor(len(arr)/2)
    pivot_height = arr[pivot]
    left, right = 0, len(arr) - 1

    while(left < right):
        # 3. ピボットと比べ、大きい要素は左へ小さい要素は右へ交換する。
        while(arr[left] < pivot_height):
            # 左側の基準値より大きい位置まで移動
            left += 1
        while(arr[right] > pivot_height):
            # 右側の基準値より小さい位置まで移動
            right -= 1

        if (left < right):
            # leftがrightを超えていない場合、leftとrightを交換
            arr[left], arr[right] = arr[right], arr[left]
            print(arr, pivot_height)
        else:
            print()
            break
    # 4. 左右2つに配列を分割してこの関数を再帰的に繰り返す。
    arr[:left] = quick_sort(arr[:left])      # ピボットの左側をクイックソート
    arr[left+1:] = quick_sort(arr[left+1:])  # ピボットの右側をクイックソート
    return arr


if __name__ == "__main__":
    # 長さ10のランダムな配列
    arr = list(range(10))
    src = random.sample(arr, len(arr))

    print(src)
    # [7, 2, 5, 3, 1, 6, 9, 4, 8, 0]

    dst = quick_sort(src)
    print(dst)
    # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

値の交換はa, b = b, aを使って1行で書いています。

print()の位置で出力すると以下のようになります。

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

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

[0, 1, 2] 2  # 3の左側


[0]
[]
[]
[4, 8, 5, 6, 7] 5  # 3の右側
[4, 5, 8, 6, 7] 5

[4]
[6, 8, 7] 6

[]
[7, 8] 7

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

コメントを入れたところがわかりやすいかと。末尾の数値はピポット(基準値)です。

4.で分割した左右の配列をそれぞれクイックソートする。 分割する度に配列が半分になるため、計算量はO(nlogn)O(n \log n)になる。

追記:サンプルコード:クイックソート - Life with Pythonのコードの方が短くてきれいです。 ピポットを基準にした交換が外部ソートっぽいですね。