C で複数列の配列を効率的にソートするには?

C での複数列配列のソート

複数列配列のソートは、Java の組み込み機能と比較すると、C での課題となります。効率的な方法の 1 つは、固定配列のソートに優れた古典的な std::qsort 関数の利用です。

コンパレータの実装

ソートを実現するには、コンパレータを次のように定義します。 qsort 関数内の 3 項文字列式。このコンパレーターは、値を順番に比較することによって複数列のソートを実行します。以下はコード スニペットです:

<code class="cpp">[](const void *arg1, const void *arg2) -> int
{
    int const *lhs = static_cast<int const *>(arg1);
    int const *rhs = static_cast<int const *>(arg2);
    return (lhs[0] < rhs[0]) ? -1
        : ((rhs[0] < lhs[0]) ? 1
        : (lhs[1] < rhs[1] ? -1
        : ((rhs[1] < lhs[1] ? 1 : 0))));
}

三項式では、まず最初の列の値 (lhs[0] と rhs[0]) を比較します。それらが等しい場合は、2 番目の列の値 (lhs[1] と rhs[1]) の比較に進みます。結果は負、ゼロ、または正で、それぞれ最初の配列を 2 番目の配列の前、同じ位置、または後に配置するかどうかを示します。

実装例

ランダム データで満たされたサイズ 10x2 の 2D 配列 ar を考えてみましょう。 std::qsort とカスタム コンパレーターを使用して、最初の列の値で配列を並べ替えることができます。

<code class="cpp">int ar[10][2];

// Populate array with random data
...

// Sort the array using qsort
std::qsort(ar, 10, sizeof(*ar),
    [](const void *arg1, const void *arg2) -> int
    {
        int const *lhs = static_cast<int const *>(arg1);
        int const *rhs = static_cast<int const *>(arg2);
        return (lhs[0] < rhs[0]) ? -1
            : ((rhs[0] < lhs[0]) ? 1
            : (lhs[1] < rhs[1] ? -1
            : ((rhs[1] < lhs[1] ? 1 : 0))));
    });</code>

複雑さの分析

最悪の場合の時間計算量std::qsort の値であり、カスタム コンパレータは O(n log n) です。ここで、n は 2D 配列の行数です。ただし、配列がほとんどソートされている場合など、特定のシナリオでは、平均時間の複雑さが大幅に低下する可能性があります。

結論

std::qsort とカスタム コンパレータを使用すると、C で複数列の 2D 配列を効率的に並べ替えることができます。 Java の組み込みソート機能ほど便利ではありませんが、この方法はデータ順序付けアプリケーションに堅牢でパフォーマンスの高いソリューションを提供します。

以上がC で複数列の配列を効率的にソートするには?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。