> udemyで学習する

クイックソートとは?【アルゴリズム紹介・Pythonによる実行】

本記事はPythonのクイックソートについて、学生エンジニアが初心者の方へ向けて優しく解説しています。ソートとは数値や文字列を昇順や降順に並べ替えることで、プログラミングを学ぶ上で非常に重要な道具です。ソートの中でも極めて重要なクイックソートを一緒に学習しましょう。

クイックソートとは?

クイックソートは、様々なソートアルゴリズムの中でも、非常に高速でよく利用されている整列アルゴリズムです。
「クイック」という言葉からその速さが理解できるかと思います。

クイックソートは、下の動画が非常にわかりやすくて非常に理解しやすいです。
クイックソートの概念とその高速な処理速度を動画で感じてみてください。


いかがでしたでしょうか。
動画からもわかるように、クイックソートは「pivot」といわれる基準の要素が非常に重要となります。
この「pivot」を利用して、入れ替えを行い、分割を繰り返すアルゴリズムがクイックソートです。
クイックソートの一連の流れをまとめました。

1.「pivot」を決定する
2.左から要素を順番に調べ、「pivot」以上であればそのインデックスをiとする。
3.左から要素を順番に調べ、「pivot」以下であればそのインデックスをjとする。
4−1.iがjより左ならば、要素を入れ替え「2」の処理へ戻る。(「2」はiの一つ右の要素から、「3」はjの一つ左の要素から探索を再開)
4−2.iがjより右ならば、iの左側を境にリストを分割(パーテーション)。分割したそれぞれのグループに対して「1」の処理へ戻る。ここで、1以下の要素数のグループができた場合、そのグループは確定とする。全てのグループが確定した場合、ソート完了。

4−2で出てきた分割する処理のことをパーテーション(partition)といいます。

クイックソートの計算量

平均計算時間最悪計算時間最良計算時間
O(n*log(n))O(n2O(n*log(n))

クイックソートの計算量は「O(n*log(n))」であり、比較回数は「(n+1)*n/2」となります。また、クイックソートは安定性のない整列アルゴリズムです。

クイックソートの欠点

非常に早い整列アルゴリズムですが、メモリが多く必要となることが1番の欠点です。
また、基準となる「pivot」の決め方により処理速度が左右されます。

Pythonコード【パーテーションの実装】

まずは、パーテンションを実装します。
パーテーションはリストを分割する処理のことですが、定義するパーテンションの関数の実装内容は以下の2点になります。
・「pivot(ピボット)」の決定
・分割
本ソースコードでは「pivot」をリストの1番最後の要素に決めることとしました。(場合によって「pivot」の決め方は使い分けることが一般的です)

def partition(nums, beginning, ending):
    i = beginning - 1
    pivot = nums[ending]
    for j in range(beginning, ending):
        if nums[j] <= pivot:
            i += 1
            nums[i], nums[j] = nums[j], nums[i]
    nums[i + 1], nums[ending] = nums[ending], nums[i + 1]
    return i+1

Pythonコード【クイックソート関数】

def quick_sort(nums, beginning, ending):
    if beginning < ending:
        pivot_index = partition(nums, beginning, ending)
        quick_sort(nums, beginning, pivot_index - 1)
        quick_sort(nums, pivot_index + 1, ending)
    return nums

上記がPythonを用いて作成したバケットソートの関数です。
再帰関数といわれる、関数の中で関数を利用する処理を行っています。

再帰関数と聞くと難しく感じますが、
分割した前後のグループの中の要素を、もう一度順序を並べ替えるために、
関数を関数の中で再度実行しているだけで、意外と簡単です。

クイックソートの実行例

上記で作成した関数を使用して、実際にクイックソートをPython環境で実行してみました。
下記がそのコードと実行結果です。

def partition(nums, beginning, ending):
    i = beginning - 1
    pivot = nums[ending]
    for j in range(beginning, ending):
        if nums[j] <= pivot:
            i += 1
            nums[i], nums[j] = nums[j], nums[i]
    nums[i + 1], nums[ending] = nums[ending], nums[i + 1]
    return i+1

def quick_sort(nums, beginning, ending):
    if beginning < ending:
        pivot_index = partition(nums, beginning, ending)
        quick_sort(nums, beginning, pivot_index - 1)
        quick_sort(nums, pivot_index + 1, ending)
    return nums


if __name__ == '__main__':
    nums = [55, 23, 19, 76, 3, 77, 19]
    print(quick_sort(nums, 0, len(nums) - 1))
【実行結果】
[3, 19, 19, 23, 55, 76, 77]

実行結果から、
20行目で宣言した[55, 23, 19, 76, 3, 77, 19]のリストを昇順に上手くソートできていることがわかります。

ということで、本記事はクイックソートについて、Pythonのコードを使用しながらまとめました。
最後まで読んでいただき、ありがとうございました\(^o^)/

超オススメのPC用品

PCを操作する上で、トラックボールマウスが非常におすすめです!
僕も感動したこのマウスを、騙されたと思って使ってみてください!(^^)

外部モニターで2倍以上の効率化が見込めます!
安いものだと、たったの1万円前後なのでおすすめですよー!\(^o^)/

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です