Pythonでクイックソートを実装する方法【動画作成方法付き】

  • このエントリーをはてなブックマークに追加
Advertisements

Pythonで学ぶアルゴリズム、ソート第5段は「クイックソート」です。クイックソートは再帰的プログラミングを使って配列の種類によっては比較的高速にソートできるアルゴリズムです。ここではPythonで動画を作る方法を紹介しながら理解する事を目標とします。

こんにちは。wat(@watlablog)です。ここでは有名なソートであるクイックソートのアルゴリズムを学びます

クイックソートの概要

特徴や計算量

クイックソートQuick sort)とは、任意の適当な基準値ピボット)を決め、基準値よりも小さいグループと大きいグループに分けて並べ替えを行う特徴を持つアルゴリズムです。

グループ分けは配列がそれ以上分割できなくなるまで繰り返し行うため、一般に再帰処理を使ったプログラミングがされます。

配列を分割しながらソートしていく分割統治法の一種でもあります。

再帰処理についてはマージソートで説明しましたので、まだ曖昧という方は是非「Pythonでマージソートの挙動を可視化してスッキリするページ」の記事をご覧ください。

クイックソートはその他のソートと比べて高速と言われており、平均計算量は\(O(N \log N)\)です。しかし、データの初期並びやピボットの選び方によってばらつきはあり、最悪計算量は\(O(N^{2})\)です。

また、同一値の順番がソート後に入れ替わる可能性もあり、マージソートと違って安定ソートではありません。

クイックソートの手順

コードを書く前に、クイックソートの手順を確認します。

クイックソートは、まず始めに配列の中からピボットと呼ばれる基準値を選びます。その後、基準値より小さい値を左側に、基準値より大きい値を右側に順番に移動させます。
この操作を図解したものを下に示します。

グループ分けの図

この操作を大小グループ毎にこれ以上分割できない最後まで繰り返す(再帰処理)と、ピボットの位置が全て確定され、全ての数のソートが完了します。

以下の動画は10個のデータに対するクイックソートの動画です。半分ずつ処理が進んでいく様子がわかります…かね?わかりにくいかも。

10データに対するクイックソートの動画

データが少ないと動画ではよくわかりませんが、後半に100個のデータを使った動画とその作り方を載せています。

Pythonでクイックソートをするコード

Advertisements

クイックソートの関数

ここからPythonでクイックソートをコーディングしていきます。

以下の全コードには、def quick_sort()にソートしたい配列(リスト)を渡して、ソート結果を受け取る形式で書いています。

pivotはリストの中心を使う仕様にしていますが、クイックソートはピボットの選び方で性能に差が出ます。改良のためにランダムに選ぶか、ランダムに数個選んだ中央値を使うか…といった選び方があるとの事。

いずれもpivot部分の変更で実装可能です。

以下が結果。ソートされました。

クイックソートの動画を作成するコード

ソートアルゴリズムは動画にするとなぜか癒されるので、今回も恒例行事として動画作成コードを紹介します。

マージソートの時は再帰処理をそのまま使って動画を作成していましたが、かなり無理やり感がありました。今回は再帰を非再帰に書き換える事で、自然と画像保存ができるようにしました。

再帰を非再帰にする方法は以下のQiita記事を参考にさせて頂きました。ありがとうございます。

「Qiita:Python 再帰関数から非再帰関数への変換を考える

全コードはこちら。

コードを実行すると、movie-quick-sort100.gifという動画が作成されます。是非色々なデータで遊んでみてください。

100データに対するクイックソートの動画

まとめ

Advertisements

この記事ではこれまで学んだ再帰プログラミングを使いながら、クイックソートをPythonで書いてみました。

また、ソート処理を可視化するために非再帰に変換、動画を作成するコードも作ってみました。

ソートアルゴリズムはプログラミング言語に標準で備わっている場合がほとんどですが、あえてアルゴリズムを学ぶのは基本情報等の資格取得目的以外にもプログラミングの学習として良いのではないでしょうか。

クイックソートを書けるようになりました!
Twitterでも関連情報をつぶやいているので、wat(@watlablog)のフォローお待ちしています!

  • このエントリーをはてなブックマークに追加

SNSでもご購読できます。

コメントを残す

*