私が（簡単に）読んだことから、Java と Python はどちらも標準ライブラリで timsort を使用しているように見えますが、C の stdlib のソート方法は qsort と呼ばれていました。
現在、一般的な言語が標準ライブラリに実装しているアルゴリズムは何ですか? また、なぜそのアルゴリズムを選択したのですか? また、Cはクイックソートから逸脱しましたか?
この質問には「[I] が直面している実際の問題」がなく、一部の人にはオープンエンドに見えるかもしれませんが、特定のアルゴリズムが標準として選択される方法/理由を知ることは非常に便利ですが、比較的教えられていないようです。また、言語固有 (データ型?) およびマシン固有 (キャッシュ ヒット?) の問題に対処する詳細な回答は、ユニが説明するよりも、さまざまな言語とアルゴリズムがどのように機能するかについてより多くの洞察を提供するように感じます。
C は、 で使用されるアルゴリズムを特定していませんqsort。
現在の glibc (2.17) では、qsortメモリを割り当て (mallocまたはalloca必要なメモリが非常に小さい場合)、マージ ソート アルゴリズムを使用します。メモリ要件が高すぎる場合、またはmalloc失敗した場合は、クイックソート アルゴリズムを使用します。
私のマシンの C ライブラリはqsort、heapsort、 、および を提供し、 man ページmergesortで次のように述べています。
および関数は
qsort()、qsort_r()パーティション交換ソートの変形である CAR Hoare の「クイックソート」アルゴリズムの実装です。特に、DE Knuth のAlgorithm Qを参照してください。クイックソートにはO(n lg n)平均時間がかかります。この実装では、中央値選択を使用して、O(n 2 )の最悪の動作を回避します。この
heapsort()関数は、選択ソートの変形である JWJ William の「ヒープソート」アルゴリズムの実装です。特に、DE Knuth のアルゴリズム Hを参照してください。ヒープソートには、最悪のケースでO(n lg n)の時間がかかります。唯一の利点qsort()は、追加のメモリをほとんど使用しないことです。whileqsort()はメモリを割り当てませんが、再帰を使用して実装されます。この関数には sizeバイト
mergesort()の追加メモリが必要です。nel * widthスペースが限られている場合にのみ使用してください。このmergesort()関数は、既存の順序を持つデータ用に最適化されています。最悪の場合の時間はO(n lg n)です。その最良のケースはO(n)です。通常、
qsort()は よりも速く、 は よりもmergesort()高速ですheapsort()。メモリの可用性とデータ内の既存の順序により、これが正しくない場合があります。
実装の具体的な詳細を確認したい場合は、オープン ソースの C ライブラリがたくさんあります。
「システム X がアルゴリズム Y を選択した理由」に関しては、意味のある答えを出すのはかなり難しい質問です。ドキュメントで理論的根拠を見つけることができなかった場合は、設計者に直接尋ねる必要があります。
qsort()についてC11標準でクイックスキャンを行いましたが、qsort()実装方法とアルゴリズムの予想される時間/空間の複雑さに関する参照が見つかりませんでした。言わなければならないのは、コンパレータ機能に関する特定の条件についてでした。
つまり、実装では、qsort() に適合する任意のコンパレータ ベースのアルゴリズムを選択できます。たとえば、実装では、バブル ソートなどの単純なアルゴリズムを使用して qsort() を実装することを選択できますが、これは実際のクイック ソートほど効率的ではありません。結論として、実際のアルゴリズムを決定するのは実装次第です。