ソートのアルゴリズムであるクイックソートについて
できるだけ分かりやすくなるよう心がけて解説していきます.
クイックソートの考え方
クイックソートは次のような処理を行っています
- 1. バラバラなデータからランダムな数(ピボット)を選択する.
- 2. 選択した数より大きいグループと小さいグループに分ける
- 3. 2つのグループそれぞれに対して,1,2の処理を行い,さらに分割する
このように,ランダムな数を選択->大小2グループに分割->
それぞれのグループを更に分割
と,分割を繰り返していくことでソートが完了します.
ソースコード
#include <stdio.h> // data1とdata2を入れ替える void swap(int *data1, int *data2) { int tmp = *data1; *data1 = *data2; *data2 = tmp; } // ピボットのIDを選ぶ.この関数の中身を変えることで // クイックソートの性能が変化する. int choose_pivot_id(int data[], int leftID, int rightID) { return leftID; } // data[leftID]~data[rightID]までのデータを // pivotより大きいグループと小さいグループに分ける // pivotがある場所のIDを返す int partition(int data[], int leftID, int rightID, int pivotID) { int pivot = data[pivotID]; // いったんpivotを右端に保存しておく swap(&data[pivotID], &data[rightID]); // 左端から見て行き,pivot以下のデータを // 左へ移動していく int p = leftID; int i; for(i = leftID; i <= rightID-1; i++){ if(data[i] <= pivot){ swap(&data[i], &data[p]); p++; } } // pがグループの境界になるので // 保存しておいたpivotをpの位置に移動する swap(&data[p], &data[rightID]); return p; } void quick_sort(int data[], int leftID, int rightID) { if(leftID >= rightID) return; // ピボットのIDを選ぶ int pivotID = choose_pivot_id(data, leftID, rightID); // pivotより大きいグループと小さいグループに分ける int p = partition(data, leftID, rightID, pivotID); // 左側をクイックソート quick_sort(data, leftID, p-1); // 右側をクイックソート quick_sort(data, p+1, rightID); } int main(void) { int data[] = {3,4,5,1,2}; int i; quick_sort(data, 0, 4); for(i = 0; i < 5; i++){ printf("%d\n", data[i]); } return 0; }
ソースコード解説
partition()
partition()は次のような処理をしています.
まず,ピボットをいったん右端に移動し,保存しておきます.
次にiとpを左端にセットします.
そしてiを動かし左から順に見て行き,ピボット以下のデータを
検索します.
ピボット以下のデータが見つかったらpの位置と入れ替えます.
データ入れ替えたらpの位置を一つ右へ動かします.
ピボット以下のデータを検索->入れ替え->p++を繰り返します.
この処理を繰り返していくことで,最終的に
pの位置を境にして,左はピボット以下,右はピボットより
大きいデータとなります.
最後にpの位置と,保存しておいたピボットを入れ替えます.
これでピボットより左はピボット以下,
ピボットより右はピボットより大きいデータとなります.