クイックソート

クイックソートは、整列のアルゴリズムのひとつです。整列のアルゴリズムとは、あるルールに基づいてデータを並び替えることを指しますが、クイックソートは数ある手法の中でも非常に高速なアルゴリズムとして広く使用されています。

クイックソートでは、まずピボットとよばれる基準値を任意に決定し、基準値よりも大きな値のグループと小さな値のグループに分けます。そして、それぞれのグループ内で同様の処理を繰り返し、すべてのグループのデータ数が1つになれば整列完了です。

例えば、「4・1・5・2・6・7・3」という数列を昇順に並び替える場合を考えてみます。ピボットを先頭の「4」と設定した場合、まずは左端と右端から、それぞれ「4」以上の値と「4」未満の数字を探索していき、見つかった時点で数字を交換します。

初めに「4」と「3」が交換され、次に「5」と「2」の交換が行われますが、左右の探索が交差した時点で探索は終了となるため、交換後の数列は「3・1・2・5・6・7・4」となります。そして、探索が交差した「2」と「5」の間で分割し、「3・1・2」と「5・6・7・4」の2つのグループ内で再びピボットを選び、同じ処理を繰り返していくことで整列されていきます。

なお、クイックソートは整列のアルゴリズムの中でも高速な手法ですが、安定したアルゴリズムではなく、その処理時間はピボットの選び方に大きく左右されます。

例えば、10個のデータの並べ替えを行う場合、初めのグループ分けで5個ずつのデータに分割し、その次にそれぞれ2個と3個に分割できれば非常に効率的です。しかし、初めのグループ分けで1個と9個のデータに分割してしまうと非効率的で、最悪の場合はバブルソート並みの計算時間がかかる恐れがあります。

ピボットの選択方法は、先頭の値やランダムで設定することもありますが、最悪の場合を回避するためには選び方を工夫する必要があります。ただし、ピボットの選択方法が複雑だと処理時間がかかるという本末転倒な結果となるため、一般的にはデータの先頭・中央・末尾の3つの中央値を使用することが多いです。