[Python] クイックソート アルゴリズム書いて見た

 

アルゴリズムの勉強をしていて、クイックソートが出てきたので実際にPythonで書いてみました。

開発環境

  • Python 3.6.4

 

クイックソートとは

ランダムな数値の配列から、基準となる数値(以下、ピボット)を決めます。

ピボット以外の数値を、「ピボットよりも小さい数値」・「ピボット以上の数値」の2つのグループに分けます。そして、それらのグループを以下のように配置します。

「ピボットよりも小さい数値」「ピボット」「ピボット以上の数値」

あとは、「ピボットよりも小さい数値」「ピボット以上の数値」をそれぞれソートすれば完成です。それぞれをソートする場合も、クイックソートを使います。

難しいですね。。。

下の図を参考にしてください(手書きですみません。。。)

下波線が、ピボットを表しています。

 

コード例

 

注意するべき点は、再帰的にquick_sortメソッドを呼び出していることです。

上の画像を見ながらコードを追っていくと、わかりやすと思います。

再帰関数の説明は、以下の記事を参照してください。

再帰関数とは

2018.07.05

まとめ

実際に、アルゴリズムを書いてみるとしっかりと頭に入ってきます。おすすめです。

コメントを残す

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

CAPTCHA