【Python】クイックソート【アルゴリズム】

この記事は約2分で読めます。

クイックソートについて

概要

  • 分割統治法に分類される
  • 計算量はO(nlogn)〜O(n^2)
  • 計算量はピボットの選択により変動する
  • ちょうど半分になるような値をピボットとして選ぶと効率が良い
  • 他のソートアルゴリズムと組み合わせて用いられる
  • 並列処理が可能

ソートの流れ

  • リストの中から要素を1つ選ぶ
  • その値より大きいものと小さいリストに分割する
  • 分割されたそれぞれのリストに対して、同様の処理を再帰的に行う
  • これ以上分割できない段階まで分割したリスト群を結合するとソート済みの結果を得られる

コード

 

[1]:要素数が1以下の場合はそのまま返す

分割を繰り返していくと、最後は全てのリストの要素数が1になります。

[2]:分割されたリスト群を結合

[pivot]*sameについて、ピボットと同じ値がいくつあったかがsameに保存されています。

sameの数だけ掛け算して結合しています。

leftはピボットよりも小さい値が、rightはピボットよりも大きい値が分割されて格納されています。

そのため、left+ピボット+rightとすることで左から小さい順(昇順)にソートすることができます。

 

 

参考

こちらの書籍を用いて学習しています。

ピボットでの分割処理について、書籍の中ではリストの内包表記を用いてよりシンプルな実装方法が紹介されています。

コードを書くとき、人それぞれによく使っているライブラリや書き方があると思います。

他の方が書いたコードを読む時に自分が使ったことのないライブラリや書き方だと、非常に読みにくいと感じますが、

普段が自分が使わないものや書き方をなるべくたくさん読んだり取り入れることで、少しでもコードを読むスピードが上がるのではないかと思います。

コメント