Array.sort Sortierstabilität in verschiedenen Browsern

Question

Welche Stabilität hat Array.sort in verschiedenen Browsern? Ich weiß, dass die ECMA-Skriptspezifikation nicht angibt, welcher Algorithmus verwendet werden soll, und auch nicht, ob die Sortierung stabil sein soll.

Ich habe diese Informationen für Firefox unter https://developer.mozilla.org/en/Core_JavaScript_1.5_Reference/Global_Objects/Array/sort gefunden, die angibt, dass Firefox eine stabile Sortierung verwendet.

Kennt jemand über IE 6/7/8, Chrome, Safari?

Answer 1

Simple test case (ignorieren Sie die Überschrift, der zweite Satz von Zahlen sollte sequentiell sein, wenn die Sortierung des Motors stabil ist).

IEs Sortierung war stabil, solange ich es jemals benutzt habe (also IE6). Überprüfen Sie erneut in IE8 und es scheint immer noch der Fall zu sein.

Und obwohl die Mozilla-Seite, auf die Sie verlinken, sagt, dass die Sortierung von Firefox stabil ist, sage ich definitiv, dass dies vor Firefox 2.0 nicht immer der Fall war.

Einige kursorisch Ergebnisse:

• IE6 +: stabil
• Firefox < 3: instabil
• Firefox> = 3: stabil
• Chrome < = 5 (dh alle Versionen bis heute): instabil
• Opera < 10: instabil
• Opera> = 10: stabil
• Safari 4: stabile

Alle Tests unter Windows. auch

Siehe:

• Fast stable sorting algorithm implementation in javascript

Answer 2

Wenn Sie nach einer Liste von Browsern suchen, in denen Sie einen nicht nativen Sortieralgorithmus verwenden sollten, ist mein Vorschlag nicht.

Führen Sie stattdessen eine Sortierungsprüfung durch, wenn das Skript geladen wird, und treffen Sie Ihre Entscheidung.

Da die Spezifikation in dieser Hinsicht kein bestimmtes Verhalten erfordert, ist sie nicht immun gegen spätere Änderungen, selbst innerhalb derselben Browserzeile.

Sie könnten einen Patch an http://www.browserscope.org/ senden, um solche Tests in ihre Suite aufzunehmen. Aber auch hier ist die Feature-Erkennung der Browser-Erkennung überlegen.

Answer 3

Ich möchte einen Trick teilen, den ich routinemäßig in C/C++ für qsort() verwende.

JS 'sort() erlaubt die Angabe einer Vergleichsfunktion. Erstellen Sie ein zweites Array der gleichen Länge und füllen Sie es mit steigenden Zahlen von 0.

function stableSorted(array, compareFunction) { 
    compareFunction = compareFunction || defaultCompare; 
    var indicies = new Array(array.length); 
    for (var i = 0; i < indicies.length; i++) 
    indicies[i] = i; 

Dies sind Indizes in das ursprüngliche Array. Wir werden das zweite Array sortieren. Erstellen Sie eine benutzerdefinierte Vergleichsfunktion.

Es wird die zwei Elemente aus dem zweiten Array erhalten: Verwenden Sie sie als Indizes in die ursprünglichen Arrays und vergleichen Sie die Elemente.

Wenn Elemente gleich sind, vergleichen Sie ihre Indizes, um die Reihenfolge stabil zu machen.

if (a < b) 
    return -1; 
    else 
    return 1; 
    }); 

nach der Sortierung() würde das zweite Array-Indizes enthalten, die man die Elemente des ursprünglichen Arrays in stabiler sortierter Reihenfolge zugreifen können.

var sorted = new Array(array.length); 
    for (var i = 0; i < sorted.length; i++) 
    sorted[i] = array[indicies[i]]; 
    return sorted; 
} 

// The default comparison logic used by Array.sort(), if compareFunction is not provided: 
function defaultCompare(a, b) { 
    a = String(a); 
    b = String(b); 
    if (a < b) return -1; 
    else if (a > b) return 1; 
    else return 0; 
} 

Im Allgemeinen stabilen Sortieralgorithmen nur fällig werden und erfordert noch mehr zusätzlichen Speicher im Vergleich zu dem guten alten qsort. Ich denke, das ist der Grund, warum nur wenige Spezifikationen eine stabile Sortierung verlangen.