今井
今回は、ソーティングルゴリズムの一つ「クイックソート」について、触れていきます。
できるだけ簡単にわかりやすく解説していきたいと思います！
- クイックソートとは？
- ソートって何？
- 分割統治法って何？
- クイックソートの実際の処理とC言語/C++のコード
C言語/C++のソースコードは一番下にありますので必要な方はスクロールお願いします。
それでは解説に移ります！
好きなところから読む
クイックソート（Quick sort）とは？
クイックソートとは、C. A. R. Hoareさんが考案した「ソーティングアルゴリズム」の一種で、内部ソートの中では最も速いといわれているアルゴリズムです。
今井
もちろん、それ以外にも同じぐらい速いソーティング方法はあり、条件や最悪の場合などを考えればクイックソートより速くなることあります。
この記事の終わりに、ほかの高速なソーティングアルゴリズムの紹介やクイックソートとの比較などを書きますので是非ご覧ください。
ぷーにゃん
今井
例えば、優先度をつけてそれ通りにタスクを実行したいとき、ありますよね。
以下のようなタスクがこのように並んでいたらどうでしょうか？
- （優先度70）一週間後のテストの勉強をする。
- （優先度50）二週間後までの課題を終わらせる。
- （優先度20）旅行の計画を立てる。
この順に並んでいるならば上から処理していけば大丈夫ですね。
しかし、「課題が二週間後までではなく、今日までだった！」と気づいたらどうでしょう。
- （優先度70）一週間後のテストの勉強をする。
- （優先度99）「今日の24:00締め切り」の課題を終わらせる。
- （優先度20）旅行の計画を立てる。
優先度が99に上がり、優先度順ではなくなってしまいました。
ここでソートが必要になります。
- （優先度99）「今日の24:00締め切り」の課題を終わらせる。
- （優先度70）一週間後のテストの勉強をする。
- （優先度20）旅行の計画を立てる。
こんな風にソートを行い、上から優先度順に並ぶように整列します。
プログラミングしていく上で、データが数字順に並んでいたほうがいいことはたくさんあります。
そんな時、このソート、すなわち、順番どおりに並べるということが必要になります。
今回の例に挙げたような3個ぐらいのデータでは何も問題ないですが、1万、10万というデータ数を扱うことを考えるとどうでしょうか？
効率よくソートする方法を知らなければ、とっても遅いプログラムになってしまいます。
そこで登場するのが効率の良いソートの一つが、今回の主役「クイックソート」なんです。
それでは、クイックソートのアルゴリズム解説に移りましょう！
クイックソートの主な考え方をわかりやすく解説！
クイックソートは分割統治法の一種
クイックソートは分割統治法というアルゴリズムの一種です。
今井
分割統治法とは、大きな問題を小さな問題の集合ととらえて、その小さな問題をすべて解くことで元の大きな問題の答えを得ようとする手法です。
トランプを買った時の順番に並べなおすとき、皆さんならどうしますか？
私だったら以下のようにします。
- 52枚のカードを「♠スペード ♥ハート ♣クローバー ♦ダイヤ」別に分ける
- マークそれぞれの13枚（A~K）を並び替えて最後に合わせる
皆さんもこうするのではないでしょうか？
どうして、その４つのマーク別に分類するのか？
これは、単純な理由で「枚数が少ないほうが並べなおしやすいから」です。
このように52枚のカードをそのまま並び替えるのではなく、「一度4つのマーク別に分割してから、それぞれを並び替えて最後にくっつける」という手法をとるのが分割統治法の考え方です。
今回のクイックソートは、基準値をとることで元のデータを分割していきます。
クイックソートは実際何を行っているのか？
ここではクイックソートの実際の処理ではなく主な考え方について書きます。
（実際の処理は下で解説）
先ほども書きました通り、クイックソートは、元のデータを分割していく分割統治法という手法を用います。
クイックソートは、データを分割する際に、基準より大きい値と小さい値という条件で2分割します。
今井
説明のために0~19までの数字をランダムに並べ替えたものを用意します。
↓ 0～19までの数字20個（ランダム） ↓
この数字たちを、0から順に0, 1, 2, 3… 19とソートしたいと思います。
まずは、基準値（ピボット）を決める必要があります。
今回は左端の「10」を基準値としてみましょう。
基準値を決めたら、基準値より小さい値と基準値より大きい値で場合分けしていきます。
左に小さい値、右に大きい値を置いていきましょう。
そうしたら、「0~9」は左のグループに入り、「11~19」は右のグループに入ります。
基準となった「10」は右のグループに入れておきましょう。
ここまでの結果、新しい2つのグループ「x<10のグループ」「10≦xのグループ」に分割できました。
当たり前ですが、左のグループと右のグループの関係性を考えてみると、
「左のグループのどの値も、右のグループのどの値よりも小さい」
ということがわかると思います。
例えば、1(左)と19(右)を比べても、9(左)と10(右)を比べても、絶対に右のグループのデータのほうが大きい値なんです。
今井
このことがわかると、左のグループと右のグループをそれぞれソートしてくっつければ順番どおりになることがわかるのです。
先ほどのトランプの例と同じです。
今の分割を先ほどの左のグループについてもう一回行いましょう。
- 基準値を決める
- 基準値より小さいグループと大きいグループに分ける
- 基準値を大きいグループのほうに入れる
ここでも「左のグループの値 < 右のグループの値」という関係が成り立っていることに注意しましょう。
さらにこのグループとは別に、10以上のグループにもこの操作を行いましょう。
これも同じです。
そうすると、どうやらまた新しい2グループに分割できることがわかります。
これが、分割統治法の考え方「小さな問題に分割して考える」ということです。
今までの流れをまとめて、クイックソートの流れ図を書いてみましょう。
このように基準値をもとに分割するというのが、クイックソートの主な流れです。
以上より、クイックソートとは、
「基準値（ピボット）と比較して小さい値と大きい値に分ける」という処理を、分割されたグループそれぞれについて繰り返し行っていく
というソーティングアルゴリズムということもできます。
そうすると最終的にすべてグループに属するデータが1個になり、その状態こそソートされた状態なのです。
今井
クイックソートのアルゴリズム、どのように実現するか？
実際の処理方法は動画で理解した後、それと照らし合わせながらソースコードを見るのが効率的だと思います。
わかりやすい動画を張っておきますので参考にしてみてください。
クイックソートのわかりやすい解説動画
- 真ん中の値を基準値に取っている
- 基準値の取り方次第で効率が良くない場合がある
- 降順（大きい値から小さい値）になるようにソート
- 中規模のソート（4:25～）
- バブルソート、シェーカーソートとの比較（5:03～）
C言語/C++で書くクイックソート
初めに言っておきますが、こんな長いクイックソートのコードを書くより、内容的にも労力的にも、用意されているライブラリの関数を使うのがいいです。
あくまで、アルゴリズムの勉強ということにお使いくださいませ。
C++をベースに書いています。たぶんCでも動きます。
#include <stdio.h>
//値を交換する関数
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
/*クイックソート*/
void QuickSort(int A[], int left, int right)
{
// 変数定義
int Left, Right;
int pivot;
// 初期値は引数から
Left = left; Right = right;
// 基準は真ん中に設定
pivot = A[(left + right) / 2];
// ソーティング
while (1) {
// 基準より小さい値を左から見つけていく
while (A[Left] < pivot) Left++;
// 基準より大きい値を右から見つけていく
while (pivot < A[Right]) Right--;
// 見つかった値の順序が逆になったら終了
if (Left >= Right) break;
// 値を交換
swap(&A[Left], &A[Right]);
// 次の値に移動
Left++; Right--;
}
//左のデータ群を対象としてクイックソートを再帰
if (left < Left - 1) QuickSort(A, left, Left - 1);
//右のデータ群を対象としてクイックソートを再帰
if (Right + 1 < right) QuickSort(A, Right + 1, right);
}クイックソート以外の高速なソーティングアルゴリズム！
最後に、ほかの高速なソーティングアルゴリズム、また、基本的なソーティングアルゴリズムの動画をご紹介して終わりにしたいと思います。
ソーティングアルゴリズムの比較動画
これはいろいろなソーティングアルゴリズムを紹介している動画です。
左上にソート名が書いてあります。
また、ソートするデータ数や速度設定が違うので注意してください。
4番目に紹介されているのがマージソート（Merge sort）、5番目に紹介されているヒープソート（Heap sort）です。
どちらも、とても高速なソーティングアルゴリズムとして有名です。
今後紹介していけたらと思います。
