【C言語】降順でクイックソートする方法を解説

この記事では、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

このように、降順でのクイックソートを実装することで、配列を降順にソートすることができます。

目次から探す