tetoblog 
本記事はPythonのクイックソートについて、優しく解説しています。ソートとは数値や文字列を昇順や降順に並べ替えることで、プログラミングを学ぶ上で非常に重要な道具です。ソートの中でも極めて重要なクイックソートを一緒に学習しましょう！
クイックソートとは？
クイックソートは、様々なソートアルゴリズムの中でも、非常に高速でよく利用されている整列アルゴリズムです。
「クイック」という言葉からその速さが理解できるかと思います。
クイックソートは、下の動画が非常にわかりやすくて非常に理解しやすいです。
クイックソートの概念とその高速な処理速度を動画で感じてみてください。
いかがでしたでしょうか。
動画からもわかるように、クイックソートは「pivot」といわれる基準の要素が非常に重要となります。
この「pivot」を利用して、入れ替えを行い、分割を繰り返すアルゴリズムがクイックソートです。
クイックソートの一連の流れをまとめました。
１．「pivot」を決定する
２．左から要素を順番に調べ、「pivot」以上であればそのインデックスをiとする。
３．左から要素を順番に調べ、「pivot」以下であればそのインデックスをjとする。
４−１．iがjより左ならば、要素を入れ替え「２」の処理へ戻る。（「2」はiの一つ右の要素から、「3」はjの一つ左の要素から探索を再開）
４−２．iがjより右ならば、iの左側を境にリストを分割（パーテーション）。分割したそれぞれのグループに対して「1」の処理へ戻る。ここで、1以下の要素数のグループができた場合、そのグループは確定とする。全てのグループが確定した場合、ソート完了。
４−２の分割する処理のことをパーテーション（partition）といいます。
クイックソートの計算量
| 平均計算時間 | 最悪計算時間 | 最良計算時間 |
| Ｏ（n*log(n)） | Ｏ（ｎ2） | Ｏ（n*log(n)） |
クイックソートの計算量は「Ｏ（n*log(n)）」であり、比較回数は「(n+1)*n/2」となります。また、クイックソートは安定性のない整列アルゴリズムです。
クイックソートの欠点
非常に早い整列アルゴリズムですが、メモリが多く必要となることが１番の欠点です。
また、基準となる「pivot」の決め方により処理速度が左右されます。
Pythonコード【パーテーションの実装】
まずはパーテンションを実装します。
パーテーションはリストを分割する処理のことですが、定義するパーテンションの関数の実装内容は下の２点です。
・「pivot（ピボット）」の決定
・分割
本ソースコードでは「pivot」をリストの１番最後の要素に決めることとしました。（場合によって「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+1Pythonコード【クイックソート関数】
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]実行結果から、
２０行目で宣言した[55, 23, 19, 76, 3, 77, 19]のリストを昇順に上手くソートできていることがわかります。
ということで、本記事はクイックソートについて、Pythonのコードを使用しながら紹介しました。
最後まで読んでいただき、ありがとうございました＼(^o^)／
超オススメのPC用品
PCを操作する上で、トラックボールマウスが非常におすすめです！
僕も感動したこのマウスを、騙されたと思って使ってみてください！(^^)
外部モニターで２倍以上の効率化が見込めます！
安いものだと、たったの１万円前後なのでおすすめですよー！＼(^o^)／
