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

2023-09-132024-08-25

クイックソートは、効率的なソートアルゴリズムであり、平均計算量がO(n log n)です。C言語でクイックソートを実装することで、配列を昇順または降順に並べ替えることができます。

中央値を求めるには、まず配列をクイックソートでソートします。ソート後、配列の要素数が奇数の場合は中央の要素が中央値となり、偶数の場合は中央の2つの要素の平均を取ります。

クイックソートを用いることで、効率的に配列の中央値を求めることが可能です。

この記事でわかること

クイックソートを用いた中央値の求め方とその位置の特定方法
クイックソートを応用した効率的な中央値計算の実装例
大規模データセットやリアルタイムデータ処理での中央値計算の応用例
クイックソートの利点と欠点、および他の中央値計算方法との比較

目次から探す

クイックソートを用いた中央値の求め方

クイックソートでの中央値の位置

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

中央値を求める際には、ソートされた配列の中央の要素を取得します。

配列の要素数が奇数の場合は中央の1つの要素が中央値となり、偶数の場合は中央の2つの要素の平均を取ります。

スクロールできます

配列の要素数	中央値の位置
奇数	中央の要素
偶数	中央の2要素の平均

中央値を求めるためのクイックソートの応用

クイックソートを用いて中央値を求める際には、完全にソートする必要はありません。

中央値の位置がわかれば、その位置までソートを行い、他の部分は無視することができます。

これにより、計算量を削減し、効率的に中央値を求めることが可能です。

実装例：クイックソートで中央値を求める

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

#include <stdio.h>
// 配列を分割する関数
int partition(int array[], int low, int high) {
    int pivot = array[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (array[j] <= pivot) {
            i++;
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
    int temp = array[i + 1];
    array[i + 1] = array[high];
    array[high] = temp;
    return i + 1;
}
// クイックソートの実装
void quickSort(int array[], int low, int high) {
    if (low < high) {
        int pi = partition(array, low, high);
        quickSort(array, low, pi - 1);
        quickSort(array, pi + 1, high);
    }
}
// 中央値を求める関数
double findMedian(int array[], int size) {
    quickSort(array, 0, size - 1);
    if (size % 2 == 0) {
        return (array[size / 2 - 1] + array[size / 2]) / 2.0;
    } else {
        return array[size / 2];
    }
}
int main() {
    int data[] = {3, 1, 4, 1, 5, 9, 2, 6, 5};
    int size = sizeof(data) / sizeof(data[0]);
    double median = findMedian(data, size);
    printf("中央値は: %f\n", median);
    return 0;
}