schedule2019-05-13

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

Pythonアルゴリズム

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

クイックソート

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

bunkasu

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

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

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

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

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

ソートのアニメーション

quick-sort

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

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

眺めていられるクイックソートのシミュレーション|JavaScript

コード

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

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


def quick_sort(arr):
    """ クイックソート 
    """
    if len(arr) < 2:
        # 1. 走査する配列長が0か１の場合戻る。
        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. 左右２つに配列を分割してこの関数を再帰的に繰り返す。
    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]