17

コードが実行されているターゲット実装がわからない JavaScript (他の場所ではある程度適用可能) では、基になる並べ替えアルゴリズム (の) が安定しているかどうかを検出する機能があり、仕様Array.sortに従っていることだけを知っています。 ?

webkit (1) (2)で 2 つのテストを見つけることができましたが、これらのテストの信頼性はどの程度ですか? (このチェックはPCPで行うことができますか?) 数学的に正しい解決策を探しています。

より高度なソート アルゴリズムでは、ソース配列の長さに応じてサブアルゴリズムを変更できるため (Timsort など)、これは難しい問題です。私が実行したすべてのテストでGoogle Chromeのソートが安定していることが示されているので、私は混乱していますが、私が見たすべてのドキュメントは、それが不安定であると述べています（ソースが理由を教えてくれます）。

(通常、私はこの戦略を使用してソートを安定させます。パフォーマンスへの影響は小さいですが、ときどき顕著になります)

さまざまな実装でソートするためのソース コード:
4

4 に答える 4

5

ブラック ボックス テストを使用して、基準に関連するすべての可能な入力をテストできない限り、プログラムが基準を満たしているかどうかを判断することはできません。ブラック ボックスは、入力を出力にマップするルックアップ テーブルを自由に持つことができるため (実世界のルックアップ テーブルのバグについては、Pentium FDIVのバグを参照)、他の入力が違反をトリガーする可能性をテストで排除できるかどうかを確認することはできません。

于 2013-05-16T06:35:10.830 に答える
0

小さな内部テストを実行して確認しますか? ウィキペディアの「ランクごと、次にスートごとのトランプ」の例を使用して、安定性を確認できます。

参照: https://en.wikipedia.org/wiki/Sorting_algorithm#Stability

安定性をチェックするために何枚のカードが必要かわかりませんが、おそらく 5 枚程度でしょうか?

于 2013-05-10T02:18:12.370 に答える