¿Qué algoritmo usa la función JavaScript Array#sort()
? Entiendo que puede tomar todo tipo de argumentos y funciones para realizar diferentes tipos de géneros, simplemente me interesa saber qué algoritmo usa el género vanilla.¿Implementación de Javascript Array.sort?
Respuesta
Si observa este error 224128, parece que Mozilla está utilizando MergeSort.
Creo que eso dependerá de la implementación del navegador al que se refiera.
Cada tipo de navegador tiene su propia implementación del motor de JavaScript, por lo que depende. Puede consultar los repositorios de código fuente para Mozilla y Webkit/Khtml para diferentes implementaciones.
IE es una fuente cerrada, por lo que puede que tenga que preguntarle a alguien en microsoft.
diferentes intérpretes pueden hacer las cosas de manera diferente en el sentido de que son ya sea con errores (es decir, no está en uso múltiple) o bien añadir o quitar caracteristicas. El método sort() es una parte estándar de Core JavaScript y estaría definido por el estándar, que los navegadores querrían seguir. –
@JasonBunting si la función se implementa * y * hace lo que debería hacer según lo definido en la especificación, los desarrolladores de navegadores pueden implementar la función como lo deseen: ya sea en forma de burbuja o de ordenación rápida. Las especificaciones de ECMA no definen el algoritmo de clasificación que se utilizará. –
Malo, entendí mal el objetivo de su pregunta. –
El estándar ECMAscript no especifica qué algoritmo de clasificación se va a utilizar. De hecho, diferentes navegadores presentan diferentes algoritmos de ordenamiento. Por ejemplo, ordenar de Mozilla/Firefox() no es stable (en el sentido de clasificación de la palabra) al ordenar un mapa. El tipo de IE() es estable.
Después de investigar un poco más, parece que, para Mozilla/Firefox, Array.sort() usa mergesort. Vea el código here.
Acabo de echar un vistazo al WebKit (Chrome, Safari ...) source. Dependiendo del tipo de matriz, se usan diferentes métodos de clasificación:
Numeric arrays (o matrices de tipo primitivo) están ordenadas usando la función de biblioteca estándar std::qsort
C++ que implementa alguna variación de quicksort (generalmente introsort).
Contiguous arrays of non-numeric type están codificados y ordenados mediante mergesort, si está disponible (para obtener una clasificación estable) o qsort
si no está disponible la opción de fusión.
Para otros tipos (matrices no contiguas y presumiblemente para matrices asociativas) WebKit utiliza selection sort (que llaman “min” sort) o, en algunos casos, ordena a través de un árbol AVL. Lamentablemente, la documentación aquí es bastante vaga, por lo que tendrías que rastrear las rutas del código para ver realmente para qué tipos se utiliza el método de clasificación.
y luego hay joyas como this comment:
// FIXME: Since we sort by string value, a fast algorithm might be to use a
// radix sort. That would be O(N) rather than O(N log N).
- Esperemos que todo aquel que en realidad “fija” Esto tiene un mejor entendimiento de tiempo de ejecución asintótica que el autor de este comentario, y se da cuenta de que radix sort has a slightly more complex runtime description que simplemente EN).
(Gracias a phsource por señalar el error en la respuesta original.)
En Min Sort, repetidamente encuentra el elemento mínimo de la matriz desde la posición actual hasta el final y lo intercambia con el elemento en la posición actual. Entre los dos bucles anidados, el bucle interno es para encontrar el mínimo desde la posición actual hasta el final. (el bucle j = i + 1 a n) –
Extraño comentario para encontrar de hecho. Pero el quicksort tiene ~ 7 líneas en la mayoría de los idiomas. También su enlace fuente parece estar roto. –
@ chmod700: gracias por la nota. Cambiaron el nombre del directorio. He actualizado el enlace. –
No hay ningún requisito para el proyecto JS utilizar un algorthim clasificación específica. Como muchos han mencionado aquí, Mozilla usa el tipo de fusión. Sin embargo, en el código fuente v8 de Chrome, a partir de hoy, usa QuickSort e InsertionSort, para matrices más pequeñas.
https://github.com/v8/v8/blob/master/src/js/array.js
de las líneas 807 a 891
var QuickSort = function QuickSort(a, from, to) {
var third_index = 0;
while (true) {
// Insertion sort is faster for short arrays.
if (to - from <= 10) {
InsertionSort(a, from, to);
return;
}
if (to - from > 1000) {
third_index = GetThirdIndex(a, from, to);
} else {
third_index = from + ((to - from) >> 1);
}
// Find a pivot as the median of first, last and middle element.
var v0 = a[from];
var v1 = a[to - 1];
var v2 = a[third_index];
var c01 = comparefn(v0, v1);
if (c01 > 0) {
// v1 < v0, so swap them.
var tmp = v0;
v0 = v1;
v1 = tmp;
} // v0 <= v1.
var c02 = comparefn(v0, v2);
if (c02 >= 0) {
// v2 <= v0 <= v1.
var tmp = v0;
v0 = v2;
v2 = v1;
v1 = tmp;
} else {
// v0 <= v1 && v0 < v2
var c12 = comparefn(v1, v2);
if (c12 > 0) {
// v0 <= v2 < v1
var tmp = v1;
v1 = v2;
v2 = tmp;
}
}
// v0 <= v1 <= v2
a[from] = v0;
a[to - 1] = v2;
var pivot = v1;
var low_end = from + 1; // Upper bound of elements lower than pivot.
var high_start = to - 1; // Lower bound of elements greater than pivot.
a[third_index] = a[low_end];
a[low_end] = pivot;
// From low_end to i are elements equal to pivot.
// From i to high_start are elements that haven't been compared yet.
partition: for (var i = low_end + 1; i < high_start; i++) {
var element = a[i];
var order = comparefn(element, pivot);
if (order < 0) {
a[i] = a[low_end];
a[low_end] = element;
low_end++;
} else if (order > 0) {
do {
high_start--;
if (high_start == i) break partition;
var top_elem = a[high_start];
order = comparefn(top_elem, pivot);
} while (order > 0);
a[i] = a[high_start];
a[high_start] = element;
if (order < 0) {
element = a[i];
a[i] = a[low_end];
a[low_end] = element;
low_end++;
}
}
}
if (to - high_start < low_end - from) {
QuickSort(a, high_start, to);
to = low_end;
} else {
QuickSort(a, from, low_end);
from = high_start;
}
}
};
- 1. javascript array.sort con valores indefinidos
- 2. Array.sort y Node.js
- 3. Implementación de JavaScript de emacs
- 4. JavaScript DEFLATE Implementación
- 5. Implementación del temporizador de JavaScript
- 6. ¿Implementación DOM en javascript puro?
- 7. Implementación de ejemplo de JavaScript Sandbox
- 8. ¿Qué algoritmo de clasificación utiliza el método Array.Sort() de .NET?
- 9. Implementación de XPath entre navegadores en JavaScript
- 10. Implementación de la transformación operacional (no javascript)
- 11. javascript implementación del árbol de búsqueda binaria
- 12. k-means implementación de clustering en Javascript?
- 13. SHA1 JavaScript Implementación de cadena grande
- 14. Array.sort Clasificación de la estabilidad en diferentes navegadores
- 15. Ruby: ¿Por qué Array.sort es lento para objetos grandes?
- 16. ¿Por qué Array.Sort() es tan lento en comparación con LINQ?
- 17. ¿Cómo es Array.Sort en C# tan súper rápido?
- 18. ¿Por qué los métodos Array.Sort() y Array.IndexOf() son estáticos?
- 19. ¿Hay una implementación de JavaScript nativo de document.ready() de jQuery?
- 20. Implementación de Javascript CPS (estilo de paso de continuación)
- 21. Implementación de Javascript de WS-I Reliable Secure Profile
- 22. Implementación de un mapa de árbol squarificado en javascript
- 23. pros y contras de la implementación javascript de serverside?
- 24. Implementación de una tabla de decisiones complicadas en JavaScript
- 25. implementación de javascript de cifrado, incluida la denegación plausible
- 26. ¿Qué es una buena implementación de JavaScript RDFa parser?
- 27. plantillas de URI: ¿hay una implementación rfc-6570 en javascript?
- 28. Implementación de la función Deshacer y Rehacer javascript y php
- 29. Implementación de AJAX en un único subproceso Javascript
- 30. ¿Por qué javascript no funciona en la implementación de heroku?
Esta no debería ser la respuesta aceptada. – Domi
Has comentado sobre esto 8 * años * después de que se lo pidieron. Los detalles de implementación cambian. – latortuga
@latortuga 14 - 8 = 6 – Walf