Array.sort Classificazione della stabilità in diversi browser

Qual è la stabilità di Array.sort in diversi browser. So che la specifica ECMA Script non specifica quale algoritmo utilizzare, né specifica se l’ordinamento debba essere stabile.

Ho trovato queste informazioni per Firefox all’indirizzo https://developer.mozilla.org/en/Core_JavaScript_1.5_Reference/Global_Objects/Array/sort che specifica che firefox utilizza un ordinamento stabile.

Qualcuno sa di IE 6/7/8, Chrome, Safari?

Semplice test case (ignorare l’intestazione, il secondo set di numeri dovrebbe essere sequenziale se l’ordinamento del motore è stabile).

La specie di IE è stata stabile finché non l’ho mai usata (quindi IE6). Controllo di nuovo in IE8 e sembra essere ancora il caso.

E anche se quella pagina di Mozilla a cui si fa riferimento dice che l’ordinamento di Firefox è stabile, direi sicuramente che non è sempre avvenuto prima (e compreso) di Firefox 2.0.

Alcuni risultati superficiali:

  • IE6 +: stabile
  • Firefox <3: instabile
  • Firefox> = 3: stabile
  • Chrome <= 5 (ovvero, tutte le versioni fino ad oggi): instabile
  • Opera <10: instabile
  • Opera> = 10: stabile
  • Safari 4: stabile

Tutti i test su Windows.

Guarda anche:

  • Implementazione dell’algoritmo di ordinamento stabile in javascript

Mi piacerebbe condividere un trucco che uso abitualmente in C / C ++ per qsort() .

‘Sort () di JS consente di specificare una funzione di confronto. Crea un secondo array della stessa lunghezza e riempilo con numeri crescenti da 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; 

Questo è un indice nell'array originale. Stiamo per ordinare il secondo array. Crea una funzione di confronto personalizzata.

  indicies.sort(function(a, b)) { 

Otterrà i due elementi dal secondo array: li usa come indici negli array originali e confronta gli elementi.

  var aValue = array[a], bValue = array[b]; var order = compareFunction(a, b); if (order != 0) return order; 

Se gli elementi sono uguali, confronta i loro indici per rendere stabile l'ordine.

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

Dopo l'ordinamento (), il secondo array conterrà gli indici che è ansible utilizzare per accedere agli elementi dell'array originale in ordine ordinato stabile.

  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; } 

In generale, gli algoritmi di ordinamento stabili stanno maturando e richiedono ancora più memoria extra rispetto al buon vecchio qsort. Immagino sia per questo che poche specifiche impongono un ordinamento stabile.

A partire da V8 v7.0 e Chrome 70, la nostra implementazione Array.prototype.sort è ora stabile. 🎉

In precedenza, V8 utilizzava un QuickSort instabile per array con più di 10 elementi . Ora, V8 utilizza l’algoritmo TimSort stabile.

L’unico motore JavaScript del motore principale che ha ancora un’implementazione ordinata di Array#sort instabile è Chakra, come usato in Microsoft Edge. Chakra usa QuickSort per array con più di 512 elementi . Per gli array più piccoli, utilizza un’implementazione di ordinamento inserzione stabile.

Demo: https://mathiasbynens.be/demo/sort-stability

Se stai cercando un elenco di browser in cui dovresti utilizzare un algoritmo di ordinamento non nativo, il mio suggerimento è no .

Effettua invece una sorta di controllo di integrità quando lo script carica e prendi la tua decisione.

Dato che le specifiche non richiedono un particolare comportamento a tale riguardo, non è immune da modifiche successive, anche all’interno della stessa linea del browser.

Puoi inviare una patch a http://www.browserscope.org/ per includere tali test nella loro suite. Ma ancora una volta, il rilevamento delle caratteristiche è superiore al rilevamento del browser.