Python

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

  /

クイックソートを実装してみます。

クイックソート (quicksort) は、1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。

n個のデータをソートする際の最良計算量および平均計算量はO(n log n)である。他のソート法と比べて、一般的に最も高速だといわれているが対象のデータの並びやデータの数によっては必ずしも速いわけではなく、最悪の計算量はO(n^2)である。また数々の変種がある。 安定ソートではない。

クイックソート – Wikipedia

サンプルコード

import random


data_len = 10
data = random.sample(range(1, 42), data_len)
print(data)


def quick_sort(collection):

    length = len(collection)
    if length <= 1:
        return collection
    else:

        pivot = collection.pop()

        greater, lesser = [], []
        for element in collection:
            if element > pivot:
                greater.append(element)
            else:
                lesser.append(element)

        return quick_sort(lesser) + [pivot] + quick_sort(greater)


print(quick_sort(data))

実行結果（例）

[16, 8, 11, 20, 22, 24, 40, 15, 13, 38]
[8, 11, 13, 15, 16, 20, 22, 24, 38, 40]
RELATED POST