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

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

～目次～

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

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

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

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

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

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

２. クイックソートのコード(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)))