【アルゴリズムの勉強】Pythonでクイックソートを書いてみた

学習エントリ。

Pythonでクイックソートを実装する。

クイックソートってなんぞ

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

クイックソート - Wikipedia

example_list = [5,2,10,1,18,3,7,4]
ASC, DESC = 1, 2

def quickSort(list,order):
    if len(list) <= 1:
        return list
    pivot = list[0]
    left = []
    right = []
    if order == ASC:
        for i in xrange(1,len(list)):
            if list[i] <= pivot:
                left.append(list[i])
            else:
                right.append(list[i])
        return(quickSort(left,ASC) + [pivot] + quickSort(right,ASC))
    else:
        for i in xrange(1,len(list)):
            if list[i] > pivot:
                left.append(list[i])
            else:
                right.append(list[i])
        return(quickSort(left,DESC) + [pivot] + quickSort(right,DESC))

    
        

print("ASC is...")
print(quickSort(example_list,ASC)) #[1, 2, 3, 4, 5, 7, 10, 18]
print("DESC is...")
print(quickSort(example_list,DESC)) #[18, 10, 7, 5, 4, 3, 2, 1]

ポイントっぽいところ

・リストの要素の一つをpivotとし、他のlistの要素を、それぞれpivotより大きいか小さいかを判定し、leftとrightに分ける
・left,rightをそれぞれ自身の関数に入れてソートし直す。要素数が1になるまで続ける。
・ソートし終えたleft + pivot + ソートし終えたrightを返す