c++ - 比較を変更するだけでqsortを安定させますか？

Question

重複の可能性：
標準ライブラリqsortを安定化していますか？

comp opを変更するだけで、qsortをintに対して安定させることは可能ですか？それが私のコードです。私はこれを約5〜7のサイズの非常に小さなアレイで使用しています。

static int compare( const void *a, const void *b )
{
    const int A(*(const int*)(a));
    const int B(*(const int*)(b));

    return B - A;
}

score 3 · Accepted Answer

C ++を使用している場合、stable_sort関数は安定しており、O（nlogn）パフォーマンスを備えています。

そうでなければ、インプレースクイックソートはその性質上不安定です（私はそう信じています）。ただし、追加の配列を使用して情報を格納する簡単なバリアントは安定しています。

qsort()不安定なバージョンを少なくとも1つ使用しました。これは、自分のマシンの入力ケースによって生成された結果と、入力ケースに対して生成された結果が異なるqsort()ことがわかったためです。stable_sort()

score 2 · Accepted Answer

比較演算子を変更するだけでは、クイックソートなどの不安定なソートアルゴリズムを安定させることはできません。安定した並べ替えアルゴリズムから始める必要があり、比較は重要ではありません (C++ での厳密な弱い順序付けである限り)。

score 0 · Accepted Answer

並べ替えている配列が本当に小さい場合は、別の並べ替えアルゴリズムを使用した方がよい場合があります。たとえば、次の回答を参照してください:小さな配列 (32 または 64 要素未満) の高速安定ソートおよび非常に小さなリストをソートするための高速アルゴリズムの実装。

3 に答える 3