Pythonで学ぶアルゴリズム 第21弾：並べ替え（クイックソート）

#Pythonで学ぶアルゴリズム< クイックソート >

はじめに

基本的なアルゴリズムをPythonで実装し，アルゴリズムの理解を深める．
その第21弾としてクイックソートを扱う．

クイックソート

・クイックソート：リストから任意にデータを選択し，これを基準として小さい要素と大きい要素に
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $分割し，それぞれのリストでまた同じような処理を繰り返してソートする方法．
・ピボット(pivot)：クイックソートで基準となるデータ．選び方は様々であるが，ここではリストの
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $先頭としている．

以上のことを踏まえて，次にクイックソートの一連の流れ図を示す．

実装

先ほどの手順に従ったプログラムのコードとそのときの出力を以下に示す．
今回は再帰を用いた方が非常に簡単にかけることが分かる．

コード

quick_sort.py

"""
2021/01/25
@Yuya Shimizu

クイックソート
"""

def quick_sort(data):

    #分割できなくなる(リスト要素が1以下)であれば，そのままデータを返す(並べ替えの必要なし)
    if len(data) <= 1:
        return data

    pivot = data.pop(0)     #リストの先頭をピボットとして取り出す

    # ピボットより小さいものでリストを作る
    left = [i for i in data if i <= pivot]
    # ピボットより大きいものでリストを作る
    right = [i for i in data if i > pivot]

    left = quick_sort(left)       #入力に対する左側リストを形成する
    right = quick_sort(right)   #入力に対する右側リストを形成する

    #########再帰しきった結果のみ，quick_sort関数の出力として返される
    #########それ以外のreturnは上のleft = quick_sort(right), left = quick_sort(right)
    return left + [pivot] + right


if __name__ == '__main__':
    DATA = [6, 15, 4, 2, 8, 5, 11, 9, 7, 13]

    print(f"{DATA} → {quick_sort(DATA)}")

出力

[6, 15, 4, 2, 8, 5, 11, 9, 7, 13] → [2, 4, 5, 6, 7, 8, 9, 11, 13, 15]

計算量

ピボットの選択が重要!うまく半分に分割できるようなピボットを選ぶことができると，マージソートと同様に$O(nlogn)$となる．ただし，ピボットをうまく選ぶことができないと，最悪な場合，$O(n^2)$となる．実用上は問題ないほど高速だが，多くのライブラリでは他のソートアルゴリズムと組み合わせるなど，高速化が図られているらしい．

感想

とりあえず，基本的な並べ替えのアルゴリズムはある程度，学ぶことができたのではないかと思う．この並べ替えに関するアルゴリズムについてはあと２つ残っている．【処理速度の比較】と【ビンソート】である．どんどん進めていきたい．

参考文献

Pythonで始めるアルゴリズム入門　伝統的なアルゴリズムで学ぶ定石と計算量
　　　　　　　　　　　　　　　　　　　　　　　　 増井 敏克　著　　翔泳社