『Pythonで体験してわかるアルゴリズムとデータ構造』メモその9/クイックソートの早さを知ろう

『Pythonで体験してわかるアルゴリズムとデータ構造』を読みながらアルゴリズムについて勉強する。

Pythonで体験してわかるアルゴリズムとデータ構造

第9章分割統治法によるソートの分類

この章のゴールは

• 並べ替え問題に分割統治法を応用して得られるアルゴリズムは、マージソートだけではないことについて説明できるようになる
• 第5章までに扱った整列アルゴリズムもとしてみなせることを説明できるようになる

クイックソートとは

1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。
n個のデータをソートする際の最良計算量および平均計算量はO(n\log n)である。
他のソート法と比べて、一般的に最も高速だといわれているが対象のデータの並びやデータの数によっては必ずしも速いわけではなく、最悪の計算量はO(n^{2})である。また数々の変種がある。 安定ソートではない。
クイックソート - Wikipedia

クイックソートのやり方としては、適当な数（ピボット）を要素からとってきて、そのピボットよりも大きいか小さいかでまず大きく分割する。
分割を行うと、「ピボットよりも小さい値」「ピボット」「ピボットよりも大きい値」の3種類できる。

イメージとしては以下。

クイックソートの平均計算時間は となっている。 今までのソートよりも早いのだが、それはなぜか。

クイックソートは必ず上の3パターンとなる。 それが要素が1になるまで繰り返されるソートになる。

早く要素が1になってしまえば、それだけ比較回数を抑えることができる。

この場合、桁数が7に対して処理回数が3回で交換回数が10回。 普通にバブルソートで交換するよりも断トツで早いのが分かる。

逆に最悪計算時間は ピボットに対して大きい小さいの種類が片方に寄ってしまっている場合に遭遇する。ソート済みの状態で実施すると大体こうなる。

これを見ると分かるように普通にバブルソートしているのと変わらなくなってしまう。

実装

def sort(A):
    if len(A) < 2:
        return A
    p = A[0]
    print("ピボットは{}".format(p))
    X, Y = divide(p, A[1:])
    print()
    print(X, Y, "をそれぞれ同じようにソート")
    return sort(X) + [p] + sort(Y)

def divide(p, A):
    if len(A) < 1:
        return ([],[])
    print("0番目の要素を{}を取り出す".format(A[0]),A[1:])
    X, Y = divide(p, A[1:])
    a = A[0]
    print("{}より{}が小さいか".format(p, a))
    if a < p:
        print([a] + X, Y)
        return ([a] + X, Y)
    else:
        print(X, [a] + Y)
        return (X, [a] + Y)

    
sort([4, 2, 3, 5, 1, 3, 2, 1, 7])

ピボットは4
0番目の要素を2を取り出す [3, 5, 1, 3, 2, 1, 7]
0番目の要素を3を取り出す [5, 1, 3, 2, 1, 7]
0番目の要素を5を取り出す [1, 3, 2, 1, 7]
0番目の要素を1を取り出す [3, 2, 1, 7]
0番目の要素を3を取り出す [2, 1, 7]
0番目の要素を2を取り出す [1, 7]
0番目の要素を1を取り出す [7]
0番目の要素を7を取り出す []
4より7が小さいか
[] [7]
4より1が小さいか
[1] [7]
4より2が小さいか
[2, 1] [7]
4より3が小さいか
[3, 2, 1] [7]
4より1が小さいか
[1, 3, 2, 1] [7]
4より5が小さいか
[1, 3, 2, 1] [5, 7]
4より3が小さいか
[3, 1, 3, 2, 1] [5, 7]
4より2が小さいか
[2, 3, 1, 3, 2, 1] [5, 7]

[2, 3, 1, 3, 2, 1] [5, 7] をそれぞれ同じようにソート
ピボットは2
0番目の要素を3を取り出す [1, 3, 2, 1]
0番目の要素を1を取り出す [3, 2, 1]
0番目の要素を3を取り出す [2, 1]
0番目の要素を2を取り出す [1]
0番目の要素を1を取り出す []
2より1が小さいか
[1] []
2より2が小さいか
[1] [2]
2より3が小さいか
[1] [3, 2]
2より1が小さいか
[1, 1] [3, 2]
2より3が小さいか
[1, 1] [3, 3, 2]

[1, 1] [3, 3, 2] をそれぞれ同じようにソート
ピボットは1
0番目の要素を1を取り出す []
1より1が小さいか
[] [1]

[] [1] をそれぞれ同じようにソート
ピボットは3
0番目の要素を3を取り出す [2]
0番目の要素を2を取り出す []
3より2が小さいか
[2] []
3より3が小さいか
[2] [3]

[2] [3] をそれぞれ同じようにソート
ピボットは5
0番目の要素を7を取り出す []
5より7が小さいか
[] [7]

[] [7] をそれぞれ同じようにソート
[1, 1, 2, 2, 3, 3, 4, 5, 7]