【Python】クイックソート【アルゴリズム】

  • 2021年12月15日
  • 2022年8月1日
  • Python
  • 167View
  • 0件

はじめに

クイックソートの Python サンプルコードを紹介します。

実用として最もよく使われるソート手法です。

Wikipedia クイックソート

サンプルコード

サンプルコードの紹介です。

def quicksort(xs, start, end):
    print(xs, start, end)
    if end - start <= 1:
        return xs
    pos = partition(xs, start, end)
    quicksort(xs, start, pos)
    quicksort(xs, pos, end)


def partition(xs, start, end):
    i = (start + end) // 2
    pivot = xs[i]
    p = start
    q = end - 1

    while True:
        while xs[p] < pivot and p < i:
            p += 1
        while xs[q] >= pivot and i < q:
            q -= 1
        if p == i and q == i:
            break
        xs[p], xs[q] = xs[q], xs[p]
        if p == i:
            i = q
        elif q == i:
            i = p

    return i


if __name__ == '__main__':
    xs = [2, 8, 7, 1, 3, 5, 6, 4]
    print('initial:', xs)
    quicksort(xs, 0, len(xs))
    print('sorted :', xs)
❯ python3 quicksort.py 
initial: [2, 8, 7, 1, 3, 5, 6, 4]
[2, 8, 7, 1, 3, 5, 6, 4] 0 8
[2, 1, 3, 7, 8, 5, 6, 4] 0 2
[1, 2, 3, 7, 8, 5, 6, 4] 0 0
[1, 2, 3, 7, 8, 5, 6, 4] 0 2
[1, 2, 3, 7, 8, 5, 6, 4] 0 1
[1, 2, 3, 7, 8, 5, 6, 4] 1 2
[1, 2, 3, 7, 8, 5, 6, 4] 2 8
[1, 2, 3, 4, 5, 8, 6, 7] 2 4
[1, 2, 3, 4, 5, 8, 6, 7] 2 3
[1, 2, 3, 4, 5, 8, 6, 7] 3 4
[1, 2, 3, 4, 5, 8, 6, 7] 4 8
[1, 2, 3, 4, 5, 6, 8, 7] 4 5
[1, 2, 3, 4, 5, 6, 8, 7] 5 8
[1, 2, 3, 4, 5, 6, 7, 8] 5 7
[1, 2, 3, 4, 5, 6, 7, 8] 5 6
[1, 2, 3, 4, 5, 6, 7, 8] 6 7
[1, 2, 3, 4, 5, 6, 7, 8] 7 8
sorted : [1, 2, 3, 4, 5, 6, 7, 8]

サンプルコード(副作用なし)

もうひとつ副作用なし版サンプルコードの紹介です。
インプットのリストを更新しません。
その代わり処理効率が少し劣ります。

def quicksort(xs):
    print(xs)
    if len(xs) <= 1:
        return xs
    pivot = xs[0]
    return (
        quicksort([x for x in xs if x < pivot])
        + [x for x in xs if x == pivot]
        + quicksort([x for x in xs if pivot < x])
    )


if __name__ == '__main__':
    xs = [2, 8, 7, 1, 3, 5, 6, 4]
    print('initial:', xs)
    ys = quicksort(xs)
    print('sorted :', ys)
❯ python3 quicksort_fn.py 
initial: [2, 8, 7, 1, 3, 5, 6, 4]
[2, 8, 7, 1, 3, 5, 6, 4]
[1]
[8, 7, 3, 5, 6, 4]
[7, 3, 5, 6, 4]
[3, 5, 6, 4]
[]
[5, 6, 4]
[4]
[6]
[]
[]
sorted : [1, 2, 3, 4, 5, 6, 7, 8]

おしまい!