2

ここにドキュメントがあります：

val sort : ('a -> 'a -> int) -> 'a list -> 'a list

比較関数に従って、リストを昇順で並べ替えます。比較関数は、引数が等しい場合は0を返し、最初の値が大きい場合は正の整数を返し、最初の値が小さい場合は負の整数を返す必要があります（完全な仕様についてはArray.sortを参照してください）。たとえば、compareは適切な比較関数です。結果のリストは昇順で並べ替えられます。List.sortは、（結果リストのサイズに加えて）一定のヒープスペースと対数スタックスペースで実行されることが保証されています。

現在の実装では、マージソートを使用しています。一定のヒープスペースと対数スタックスペースで実行されます。

val stable_sort : ('a -> 'a -> int) -> 'a list -> 'a list

List.sortと同じですが、the sorting algorithm is guaranteed to be stable（つまり、等しいと比較される要素は元の順序で保持されます）。

現在の実装では、マージソートを使用しています。一定のヒープスペースと対数スタックスペースで実行されます。

merge sortとにかく安定していると思いましたよね？

OCamlはどのようにnon-stable mergeソートを生成できますか？

non-statble merge sortバージョンでは、より高速ですか？

4

2 に答える 2

6

マージソートは安定していますが、ソートがマージソートを使用するという事実は、その契約の一部ではありません。「現在の実装では...を使用しています」としか書かれていないことに注意してください。将来的にマージソートを使用し続けるという保証はないためList.sort、コードで使用する場合、現在の実装でたまたま安定していたとしても、ソートが安定するという保証はありません。

安定した並べ替えを必要とするすべてのコードが を使用している限りstable_sort、Ocaml の将来のバージョン (または代替実装) が の不安定なアルゴリズムに切り替わっても、コードが壊れることはありませんsort。

于 2013-02-22T17:28:21.953 に答える
1

定義を実装から分離する必要があります。実装者は実装を変更する権利を留保しており、関数がどのように動作するように定義されているかについて、見事に注意して明確にしています。

于 2013-02-22T17:28:54.573 に答える