DB/R/統計/データサイエンス/投資話についてつらつらと

世のため自分のためのアウトプット

Python アルゴリズム

【quick sort】pythonでクイックソート

投稿日:

なっとく!アルゴリズムという本でクイックソートの章があったのでついでにpythonでスクラッチで書いてみました。

~目次~

1. クイックソートの概要

2. クイックソートのコード

1. クイックソートの概要

クイックソートはソートアルゴリズムの一つで、計算量はO(nlogn)です。

他には、同じ計算量のO(nlogn)のマージソートと、クイックソートよりも遅いO(n2)の選択ソートがあります。

クイックソートはマージソートと比べると、計算量の定数部分が小さい(速い)という特徴と、後述するピボットの選び方で計算量がO(nlogn) ~ O(n2)まで幅がありますが、平均すると0(nlogn)となり、先述の通りマージソートよりも定数部で優れているソート手法となります。

2. クイックソートのコード(python)

pythonでスクラッチで書いたソースコード。割とシンプルにできた。


def qsort(list_):
    #基本ケース
    if list_ == []:
        return []
    #再帰ケース
    pivot = list_.pop(0) #リストの先頭をピボット
    low_list = [] #ピボットより低い値を格納
    high_list = [] #ピボットより高い値を格納
    for i in list_:
        low_list.append(i) if i

jupyter notebookの%%timeで測ったら、クイックソート pythonでgoogleのトップに出てくるソースコードよりも早かったので、それなりに優秀かと思います。

試した時のコードは以下


%%time
import numpy as np
for i in range(1000):
    qsort(list(np.random.rand(1000)))

-Python, アルゴリズム
-,

Copyright© 世のため自分のためのアウトプット , 2020 All Rights Reserved Powered by STINGER.