本記事では、基本的なソートの一種である「クイックソート」のアルゴリズム解説・C言語による実装を確認していきます。
アルゴリズム解説では、図を用いた解説を行うため、イメージしやすい構成となっています。
ソートは、アルゴリズムの中でも非常に基本的な分野なので、是非この機会にマスターしましょう。
- クイックソートの基本的な情報
- アルゴリズムの流れ
- C言語による実装方法
こちらの記事で、他のソートアルゴリズムをまとめています。
アルゴリズム入門書はこの一冊で十分！
クイックソートとは
クイックソートは、ソートアルゴリズムの一種であり、マージソートと同様、分割統治法を用いてソートを行うアルゴリズムです。
基本的な情報は以下になります。
| 最悪計算時間 \(O\) | 安定性 |
| \(O(n^2)\) | 安定ではない |
最悪計算時間は\(O(n^2)\)となっていますが、平均計算時間は\(O(nlog(n))\)であるため、クイックソートは比較的高速に動作します。
ちなみに、分割統治法とは、簡単に言うと、「大きな問題をそのまま解くのではなく、小さな問題に分割して、それぞれを解くことで、最終的に大きな問題を解く方法」のことを言います。
次の章で実例をお見せするので、今はピンと来なくても大丈夫です。
クイックソートのアルゴリズム
まずは、軽く全体的な流れを確認し、その後、図を用いた説明へと移ります。
クイックソートのアルゴリズムは以下のようになります。
配列全体に対してquickSortを行う
quickSortでは以下の処理を行う
- 対象の配列をパーティションによって、左右２つの部分配列へと分割
- ①で分割した部分配列のうち、左側の配列に対してquickSortを行う
- ①で分割した部分配列のうち、右側の配列に対してquickSortを行う
quickSortの処理の中で、さらにquickSortを行うため、これは再帰的な処理になります。
文面だとよくわからないと思うので、さっそく実例を見ていきましょう。
では、サイズが８の配列で昇順ソートの具体例を見ていきます。
ここでは、配列の初期状態を次のようにします。
まずは、この配列全体を対象としてパーティションを適用し、並び替えを行います。
一応、簡単にパーティションの概要を説明しておきます。
パーティションは、配列の中で基準値を１つ決め、その基準値を境にして、それよりも小さな値を基準値の左側へ、大きな値を右側へと移動するアルゴリズムです。
アルゴリズムの詳細気になる方は、上のリンクから飛んでみてください。
では、クイックソートに話を戻します。
最初の配列に対してパーティションを適用すると、このように並び替えることができます。
次に、基準値の左右にある部分配列に対して、再びパーティションを適用します。
左右それぞれの部分配列にパーティションを適用すると、以下のようになります。
図では２つの配列に分割していますが、実際は１つの配列内で並び替えているだけなので、実際の配列はこのようになっています。
では、先ほどと同様に、２つに分かれている部分配列に対して、さらにパーティションを適用していきます。
パーティション適用後は、このようになります。
これ以上は分割できないため、ここで処理は終了します。
再度確認しておくと、図ではいくつかの配列に分割しているように図示していますが、実際には、これらの処理は1つの配列内で行われます。
クイックソートでは、以下に示すように、１つの配列の中で並び替えを繰り返します。
この点がマージソートと異なる点なので、注意してください。
ここまでがクイックソートアルゴリズムの動きとなります。
一度のパーティションで綺麗に二分割できた場合に、クイックソートの計算時間\(O(nlog(n))\)となり、高速に動作します。
逆に、パーティションで二分割した際に、左右のバランスが悪い場合は\(O(n^2)\)となり、そこまで高速ではなくなります。
１つ付け加えておくと、上で見てきた処理は、本来は再帰的な処理を行うので、上図とはパーテーションの順番が異なります。
気になる方は、コードから読み取ってください。
次の章では、これをC言語で実装していきます。
実際に自分の手で実装することで、より理解が深まるので、是非確認してみてください。
クイックソートの実装【C言語】
さっそく、プログラム全体のコードを示します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#include <stdio.h> #define N 8 // 配列の全ての要素を出力する void printArray(int A[], int n) { for (int i = 0; i < n; i++) if (i == 0) printf("%d", A[i]); else printf(" %d", A[i]); printf("\n"); } // 配列の要素を入れ替える void swap(int A[], int a, int b) { int temp; temp = A[a]; A[a] = A[b]; A[b] = temp; } // パーテーションを行う関数 int partition(int A[], int p, int r) { for (int i = p; i < r; i++) { if (A[i] <= A[r]) { swap(A, p, i); // A[p-1]とA[i]を交換する p++; } } swap(A, r, p); // A[r]とA[p]を交換する // 基準値の位置を返す return p; } void quickSort(int A[], int p, int n) { int x; if (p < n) { x = partition(A, p, n); // 基準値の位置を返り値として受け取る quickSort(A, p, x-1); quickSort(A, x+1, n); } } int main(void) { int A[N] = {4, 2, 8, 1, 7, 3, 9, 6}; printArray(A, N); quickSort(A, 0, N-1); // クイックソートを行う printArray(A, N); return 0; } |
長々としていますが、クイックソート本体は、37~44行目の quickSort関数の中で実装しています。
見ていただけるとわかるように、 quickSort 関数内で、再び quickSort 関数を実行しているため、再帰的な処理を行っています。
正直、 quickSort 関数自体はそこまで難しくなく、どちらかというと partition 関数の方がわかりづらいと思います。
自分の手を動かして確認してみることで、理解が深まると思うので、納得いくまで色々いじってみてください。
では、今回はここまでとします。
お疲れさまでした。
別のソートを確認したい方は、ソートアルゴリズム 計算量・特徴一覧をご覧ください。