In JavaScript (etwas anderswo anwendbar), wo Sie nicht wissen, welche Zielimplementierung Ihr Code läuft, gibt es eine Möglichkeit zu erkennen, ob der zugrundeliegende Sortieralgorithmus (von Array.sort) stabil ist oder nicht, nur zu wissen folgt the specification?Gibt es eine Black-Box-Methode, um festzustellen, ob ein Sortieralgorithmus stabil ist?
Ich könnte 2 Tests in Webkit (1)(2) finden, aber wie zuverlässig sind diese Tests? (Könnte diese Überprüfung mit einer PCP durchgeführt werden?) Ich bin auf der Suche nach einer Lösung, die mathematisch solide wäre.
Dies ist ein kniffliges Problem, da ein fortgeschrittener Sortieralgorithmus Subalgorithmen abhängig von der Länge des Quell-Arrays (wie Timsort) ändern kann. Ich war verwirrt, da jeder Test, den ich ausgeführt habe, gezeigt hat, dass Google Chrome stabil ist, aber die gesamte Dokumentation, die ich gesehen habe, hat gesagt, dass sie instabil ist (the source wird dir sagen warum).
(In der Regel verwenden, ich this strategy meiner Art stabil zu machen, es hat eine kleine, aber manchmal noticable Auswirkungen auf die Leistung)
Quellcode für die Sortierung in verschiedenen Implementierungen:
Sie können eine solche Bestimmung nur probabilistisch machen: Ich kann zum Beispiel einen Sortieralgorithmus 'S' definieren, der den Eingang' I' benutzt. Normalerweise "S" faßt die eigentliche Sortierarbeit zu einem stabilen Sortieralgorithmus "T" aus, aber wenn "I" gleich einem speziellen Wert "I" ist, verwendet es stattdessen eine nicht stabile Sortierfolge "U".Du wirst nie beweisen, dass "S" nicht stabil ist, außer du hast Glück und passierst "I" als Eingabe. Realistischerweise verwendet "S" wahrscheinlich stabile Sortierungen, es sei denn, "I" ist sehr lang. Auch hier werden Sie nur instabile Sortierungen beobachten, wenn Sie an entsprechend langen Eingaben testen. – apsillers
Wenn die Spezifikation besagt, dass sie nicht stabil ist, bedeutet dies nicht, dass Sie beim Sortieren des Arrays erwarten können, dass die Elemente die Reihenfolge wechseln, sondern dass Sie sich nicht darauf verlassen können. es gibt keine Versprechungen. Dass die (aktuelle) Implementierung stabil ist, bedeutet nicht, dass es immer sein wird, oder für alle Plattformen, auf denen Chrome läuft. – frozenkoi
Ich stimme @MarZab zu, dass dies ein Problem mit dem Anhalten ist. Sie könnten etwas mehr Aufmerksamkeit sehen, wenn Sie es "[Informatik]" und/oder "[Informatik-Theorie]" markieren. – apsillers