目次から探す
クイックソートのアルゴリズム
クイックソートは、効率的なソートアルゴリズムの一つです。
以下では、クイックソートのアルゴリズムについて説明します。
ピボットの選択方法
クイックソートでは、配列を分割するためにピボットと呼ばれる要素を選択します。
ピボットの選び方にはいくつかの方法がありますが、一般的には以下の方法が使われます。
- 最初の要素をピボットとする方法
- 中央の要素をピボットとする方法
- ランダムに要素を選択する方法
ピボットの選び方によって、クイックソートの性能が変わることがあります。
ピボットを基準に配列を分割する方法
ピボットを選択した後、配列をピボットを基準に分割します。
具体的な手順は以下の通りです。
- ピボットより小さい要素をピボットの左側に移動する
- ピボットより大きい要素をピボットの右側に移動する
- ピボットを正しい位置に置く
この手順を繰り返すことで、配列はソートされていきます。
再帰関数の実装
クイックソートは再帰的な処理を行うことが特徴です。
以下では、クイックソートの再帰関数の基本形と、ピボットの選択方法を考慮した再帰関数の実装について説明します。
クイックソートの再帰関数の基本形
クイックソートの再帰関数の基本形は以下のようになります。
void quickSort(int arr[], int left, int right) {
if (left < right) {
// ピボットの選択と配列の分割
int pivotIndex = partition(arr, left, right);
// ピボットの左側を再帰的にソート
quickSort(arr, left, pivotIndex - 1);
// ピボットの右側を再帰的にソート
quickSort(arr, pivotIndex + 1, right);
}
}この再帰関数では、配列の左端と右端のインデックスを引数として受け取り、配列を分割して再帰的にソートを行います。
ピボットの選択方法を考慮した再帰関数の実装
ピボットの選択方法を考慮した再帰関数の実装では、事前にピボットを選択する処理を追加します。
以下は、中央の要素をピボットとする実装例です。
int partition(int arr[], int left, int right) {
int pivot = arr[(left + right) / 2];
int i = left - 1;
int j = right + 1;
while (1) {
do {
i++;
} while (arr[i] < pivot);
do {
j--;
} while (arr[j] > pivot);
if (i >= j) {
return j;
}
swap(&arr[i], &arr[j]);
}
}
void quickSort(int arr[], int left, int right) {
if (left < right) {
int pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex);
quickSort(arr, pivotIndex + 1, right);
}
}この実装では、配列の中央の要素をピボットとして選択し、配列を分割して再帰的にソートを行います。
クイックソートの実行例
最後に、クイックソートの実行例を紹介します。
サンプルデータの準備
以下の配列を例として使用します。
int arr[] = {5, 2, 8, 1, 9};
int size = sizeof(arr) / sizeof(arr[0]);クイックソートの実行手順と結果の確認
quickSort(arr, 0, size - 1);上記のコードを実行すると、配列が以下のようにソートされます。
1, 2, 5, 8, 9以上が、再帰関数を使ったクイックソートの実装方法と実行例です。
クイックソートは効率的なソートアルゴリズムであり、再帰的な処理を行うことで高速にソートを行うことができます。