【Python】クイックソートを実装してみた

Pythonでクイックソートを実装してみました。

クイックソートは、分割統治法(divide-and-conquar)を使い一度分割し再度合体させることで高速なソートを実現します。

  1. 要素が1以下なら処理を行わない
  2. リストの1番左の値をピボットとして選択
  3. ピボット以下をサブリストleft,ピボットよりも大きい値をサブリストrightに分割する
  4. 分割した2つのサブリストに再帰的にソートを適用する
  5. 分割した2つのサブリストとピボットを合体して終了

具体的に流れを見ていきます。

コード例は以下の通り。

おわり。