c - qsort() はどのソートアルゴリズムを使用しますか?

Question

名前が示すように、関数qsort()はstdlib.h実際にクイックソートアルゴリズムを使用していますか?

Answer 1

このqsort()関数は、ライブラリの実装者が選択する任意のソート アルゴリズムを使用して実装できますが、その名前はアルゴリズムが最適に近いものであることを示唆しています。O(N ² ) アルゴリズムの使用は許容されますが、主要な QoI (実装の品質) の問題です。

qsort()インターフェイスとの比較は非常にコストがかかることに注意してください。比較の数を増やして移動の数を減らすソート アルゴリズム (ポインターをシャッフルしていない場合はコストが高くなる可能性もあります) は、パフォーマンスの低下につながる可能性があります。ただし、これはライブラリの実装者が関心を持つべき問題です。ライブラリの実装がひどい (最近ではほとんどありません) と思わない限り、心配する必要はありません。

C++sortアルゴリズムは、C の周りでリングを実行できますqsort。

Answer 2

C11 規格では指定されていません。そのため、妥当な O(n log n) は許容されます。