この記事では、C言語で降順でのクイックソートを実装する手順と具体的なコード例を紹介します。
目次から探す
降順でのクイックソートの手順
クイックソートは、効率的なソートアルゴリズムの一つであり、配列を分割して再帰的にソートすることで、要素を昇順に並べ替えます。
しかし、通常のクイックソートは昇順にソートするため、降順でソートする場合には手順を少し変更する必要があります。
以下では、降順でのクイックソートの手順について解説します。
ピボットの選択
クイックソートでは、配列の中からピボットとなる要素を選びます。
ピボットは、配列を分割するための基準となる要素です。
通常は配列の先頭や末尾の要素を選ぶことが多いですが、降順でソートする場合には、配列の中央の要素を選ぶことが一般的です。
ピボットを基準に配列を分割する
選ばれたピボットを基準に、配列を2つの部分に分割します。
ピボットよりも大きい要素は右側に、小さい要素は左側に配置します。
このとき、要素の順序を保つために、ピボットと同じ値の要素はどちらの部分にも配置します。
分割された配列を再帰的にソートする
分割された2つの部分配列に対して、再帰的にクイックソートを適用します。
つまり、各部分配列に対してピボットを選び、再び分割とソートを行います。
この再帰的な処理を繰り返すことで、配列全体がソートされます。
降順でのクイックソートの実装例
ここでは、降順でのクイックソートの実装例を示します。
以下のコードは、整数型の配列を降順でソートするクイックソート関数です。
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pivot = arr[low]; // ピボットを配列の先頭に設定
int i = low;
int j = high;
while (i < j) {
while (arr[i] > pivot) { // ピボットよりも小さい要素を探す
i++;
}
while (arr[j] < pivot) { // ピボットよりも大きい要素を探す
j--;
}
if (i <= j) {
// 見つかった要素を交換
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
// 分割された部分配列に対して再帰的にクイックソートを適用
quickSort(arr, low, j);
quickSort(arr, i, high);
}
}降順でのソート結果の確認
以下のコードは、降順でのクイックソートの実行例です。
#include <stdio.h>
int main() {
int arr[] = {5, 2, 8, 1, 9};
int n = sizeof(arr) / sizeof(arr[0]);
printf("ソート前の配列: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
quickSort(arr, 0, n - 1);
printf("\nソート後の配列: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}ソート前の配列: 5 2 8 1 9
ソート後の配列: 9 8 5 2 1このように、降順でのクイックソートを実装することで、配列を降順にソートすることができます。