目次から探す
クイックソートのアルゴリズム
クイックソートは、効率的なソートアルゴリズムの一つです。
以下では、クイックソートの手順の概要と再帰関数を使ったクイックソートの実装例について説明します。
クイックソートの手順の概要
ピボットの選択
ソート対象の配列からピボット要素を選びます。
一般的には、配列の先頭、末尾、または中央の要素を選ぶことが多いです。
ピボットを基準に分割
ピボットより小さい要素をピボットの前に、大きい要素をピボットの後ろに配置します。
この分割を行うことで、ピボットの位置が確定します。
分割された部分配列に対して再帰的にクイックソートを適用
ピボットの前後に分割された部分配列に対して、再帰的にクイックソートを適用します。
これにより、部分配列がソートされます。
ソート済みの部分配列を結合
再帰的な呼び出しが終了した後、ソート済みの部分配列を結合して最終的なソート結果を得ます。
再帰関数を使ったクイックソートの実装例
以下に、再帰関数を使ったクイックソートの実装例を示します。
void quickSort(int arr[], int low, int high) {
if (low < high) {
// ピボットの選択
int pivot = arr[high];
int i = low - 1;
// ピボットを基準に分割
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
// 要素の交換
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// ピボットの位置を確定
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
// 分割された部分配列に対して再帰的にクイックソートを適用
quickSort(arr, low, i);
quickSort(arr, i + 2, high);
}
}この実装では、再帰関数 quickSort を定義しています。
配列 arr の範囲 low から high までをソートするようになっています。
再帰呼び出しにより、部分配列がソートされ、最終的には全体の配列がソートされます。
再帰関数無しでのクイックソートの実装方法
再帰関数を使わずにクイックソートを実装する方法として、スタックを使った非再帰的な実装方法があります。
以下では、スタックを使ったクイックソートの実装方法の概要と実装例について説明します。
スタックを使った非再帰的な実装方法の概要
スタックを使った非再帰的な実装方法では、再帰呼び出しをスタックに積むことで、再帰的な処理を非再帰的に実現します。
具体的な手順は以下の通りです。
- 初期状態として、ソート対象の配列の範囲をスタックに積む。
- スタックが空になるまで以下の処理を繰り返す。
- スタックから範囲を取り出す。
- ピボットの選択と分割を行い、ピボットの位置を確定する。
- 分割された部分配列の範囲をスタックに積む。
スタックを使ったクイックソートの実装例
以下に、スタックを使ったクイックソートの実装例を示します。
void quickSort(int arr[], int low, int high) {
// スタックの初期化
int stack[high - low + 1];
int top = -1;
// 初期状態をスタックに積む
stack[++top] = low;
stack[++top] = high;
// スタックが空になるまで処理を繰り返す
while (top >= 0) {
// スタックから範囲を取り出す
high = stack[top--];
low = stack[top--];
// ピボットの選択
int pivot = arr[high];
int i = low - 1;
// ピボットを基準に分割
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
// 要素の交換
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// ピボットの位置を確定
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
// 分割された部分配列の範囲をスタックに積む
if (i + 2 < high) {
stack[++top] = i + 2;
stack[++top] = high;
}
if (low < i) {
stack[++top] = low;
stack[++top] = i;
}
}
}この実装では、スタックを使って再帰的な処理を非再帰的に実現しています。
スタックに範囲を積むことで、分割された部分配列の範囲を保持しながら処理を進めることができます。