2008-10-24 37 views
160

¿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

56

Si observa este error 224128, parece que Mozilla está utilizando MergeSort.

+77

Esta no debería ser la respuesta aceptada. – Domi

+10

Has comentado sobre esto 8 * años * después de que se lo pidieron. Los detalles de implementación cambian. – latortuga

+6

@latortuga 14 - 8 = 6 – Walf

4

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.

+0

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. –

+1

@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á. –

+0

Malo, entendí mal el objetivo de su pregunta. –

17

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.

+12

** Actualización: ** Los Firefox recientes tienen un 'Array.sort' estable; vea [esta pregunta] (http://stackoverflow.com/questions/3026281/array-sort-sorting-stability-in-different-browsers). – skagedal

+0

El punto es que el algoritmo de clasificación depende de la implementación. – cyanbeam

6

Después de investigar un poco más, parece que, para Mozilla/Firefox, Array.sort() usa mergesort. Vea el código here.

215

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.)

+0

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) –

+0

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. –

+0

@ chmod700: gracias por la nota. Cambiaron el nombre del directorio. He actualizado el enlace. –

10

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