クイックソート 【quick sort】
概要
クイックソート（quick sort）とは、与えられたデータ列を大小などの順序通りになるよう並べ替えるソート(整列)アルゴリズムの一つで、分割統治法を応用したもの。最も高速な手法の一つで、1960年に英コンピュータ科学者アントニー・ホーア(Charles Antony Richard Hoare)氏が考案した。大きな問題を小さな部分問題に分割していく「分割統治法」を利用した整列法で、データ列から適当に基準値を決め、これより大きいグループと小さいグループに分けるという手順を、分けた小さなグループに対しても再帰的に繰り返していく。
基準値の選び方には様々な方式があり、これによって比較・交換回数が左右されるが、あまり複雑な決定法だと基準値を選出するのに計算量を費やしてしまうため、単純に先頭やランダムな位置を選択することも多い。
n個の要素をソートする計算量は最良でも平均でも O（nlogn） と高速だが、最悪の場合は O（n2） になってしまう欠点もある。同じ計算量オーダーとなる整列法はヒープソートなどいくつかあるが、実際に試してみると平均的にクイックソートが高速であるとされる。
元のデータ列を格納した領域以外に別の記憶領域を必要としないインプレースソート（内部ソート）だが、通常は関数の再帰呼び出しを用いて実装するため、実用上はスタックの容量が O（logn） だけ必要となる。同じ大きさの要素の順序の維持は保証されない不安定ソートである。
例
例えば、（3,7,4,2,6,1,5）という整数列を小さい順（昇順）に並べ替える場合を考える。先頭の3を基準として、左右端から反対の端に向かって値を一つずつ基準と比較していき、左から探した3以上の値が右から探した3未満の値より左にあったら交換する。両者を比べて3以上が右にあったら探索終了となる。
3と1、7と2が交換され、（1,2,4,7,6,3,5）となる。2と4を比較して探索が終わったので、この間で2つのグループに分け、（1,2）-（4,7,6,3,5）のそれぞれに同じ操作を行う。（1,2）は（1）-（2）に、（4,7,6,3,5）は（3）-（7,6,4,5）に分かれる。
（7,6,4,5）に同じ操作を繰り返すと、（5,6,4）-（7） → （4）-（6,5）-（7） → （4）-（5）-（6）-（7） と分割されながら整列されていく。分割によってすべてのグループの要素数が1になったところで整列終了となる。このとき、端から順に小さい順に値が並んでいることが分かる。
共有ボタンをタップ