【C言語】クイックソートで中央値を求める方法を解説

2023年9月13日

この記事では、C言語のクイックソートを使って中央値を求める方法について解説します。

目次から探す

クイックソートを使った中央値の求め方

クイックソートは、効率的なソートアルゴリズムの一つです。

この記事では、クイックソートを使って中央値を求める方法について解説します。

クイックソートの実装

クイックソートは、分割統治法を用いた再帰的なソートアルゴリズムです。

以下の手順で実装されます。

ピボットの選択: ソート対象の配列から、適当な要素をピボットとして選びます。

一般的には、配列の先頭や末尾、またはランダムな位置を選ぶことが多いです。

ピボットを基準に分割: ピボットより小さい要素をピボットの左側に、大きい要素を右側に配置します。

この操作により、ピボットの正しい位置が確定します。

再帰的なソート: ピボットを基準に分割された左右の部分配列に対して、再帰的にクイックソートを適用します。

これにより、部分配列がソートされます。

結合: ソートされた部分配列を結合し、最終的なソート済み配列を得ます。

中央値を求める手順

クイックソートを使って中央値を求める手順は以下の通りです。

ソート対象の配列をクイックソートで昇順にソートします。
ソートされた配列の要素数をnとします。
ソートされた配列の中央の要素を求めます。

要素数が奇数の場合は、n/2番目の要素が中央値です。

要素数が偶数の場合は、n/2番目とn/2+1番目の要素の平均が中央値です。

サンプルコード

以下に、C言語でクイックソートを使って中央値を求めるサンプルコードを示します。

#include <stdio.h>
// クイックソートの実装
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;
        int partitionIndex = i + 1;
        quickSort(arr, low, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, high);
    }
}
// 中央値を求める関数
float findMedian(int arr[], int n) {
    quickSort(arr, 0, n - 1);
    if (n % 2 == 1) {
        return arr[n / 2];
    } else {
        return (arr[n / 2 - 1] + arr[n / 2]) / 2.0;
    }
}
int main() {
    int arr[] = {9, 5, 7, 2, 1, 8, 3, 6, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    float median = findMedian(arr, n);
    printf("中央値: %.2f\n", median);
    return 0;
}

上記のサンプルコードでは、quickSort関数で配列をクイックソートし、findMedian関数で中央値を求めています。

配列 {9, 5, 7, 2, 1, 8, 3, 6, 4} の中央値を求める場合、結果は 5.00 となります。

クイックソートは再帰的なアルゴリズムであるため、大きなデータセットに対してはスタックオーバーフローの可能性があることに注意してください。

また、本記事では中央値の求め方に焦点を当てていますが、クイックソート自体の詳細な解説は省略しています。クイックソートのアルゴリズムを詳しく知りたい方は以下の記事を参考にしてください。