Algoritmo de JavaScript "sort()" Función

Question

Recientemente, cuando estaba trabajando con JavaScript "sort()" función, encontré en uno de los tutorials que esta función no ordena los números correctamente. En lugar de ordenar los números, una función hay que añadir que compara los números, como el código siguiente: -

<script type="text/javascript"> 
function sortNumber(a,b) 
{ 
    return a - b; 
} 

var n = ["10", "5", "40", "25", "100", "1"]; 
document.write(n.sort(sortNumber)); 
</script> 

continuación, la salida se presenta como: -

1,5,10,25,40,100 

Ahora lo que no entiendo es que ¿Por qué ocurre esto? & ¿alguien puede decir en detalles en qué tipo de algoritmo se está utilizando en esta función "sort()"? Esto se debe a que para cualquier otro idioma, no encontré este problema donde la función no ordenó correctamente los números .

Cualquier ayuda es muy apreciada.

Answer 1

Bueno, si está ordenando la siguiente lista, que contiene sólo cadenas:

var n = ["10", "5", "40", "25", "100", "1"]; 

Así que cabe esperar cualquier lenguaje compararía como cadenas, lo que resulta en un orden de clasificación de:

var n = ["1", "10", "100", "25", "40", "5"]; 

Que necesita su código para utilizar una clasificación personalizada (como lo ha hecho) para convertir las cadenas de nuevo a enteros a los fines de la clasificación.

Editar

Como se mencionó puntiagudo, por defecto los JavaScript sort() method ordena los elementos alfabéticamente, incluidos los números:

Por defecto, el método sort() ordena los elementos alfabéticamente y ascendente. Sin embargo, los números no se ordenarán correctamente (40 viene antes de 5). Para ordenar los números, debe agregar una función que compare los números.

Simplemente increíble ... por lo que se requiere una ordenación personalizada incluso para una matriz de números enteros.

Answer 2

¿Y si tu n se define como:

var n = [10, 5, 40, 25, 100, 1]; 

Answer 3

El problema radica en el uso de cadenas para representar números, que hace la función de clasificación por desgracia, como por defecto. Las cadenas se ordenan alfabéticamente. La función de comparación en su código obliga a que las cadenas se evalúen como números.

lo consideraría muy mal diseño API que la función de clasificación por defecto en el tratamiento de los elementos como cadenas, pero puede ser necesario dado sistema de tipos sueltos de JavaScript ..

Answer 4

tipo de ordenación de JavaScript lexicográfico defecto, por orden alfabético. Por lo tanto, según entiendo, cada elemento se trata como una cadena. El algoritmo de clasificación interno probablemente sea quicksort o mergesort. Para poder usar quicksort necesita poder relacionar elementos entre sí, ¿es más grande que b? En el caso de cadena, este orden ya está implementado.

Dado que es posible que desee ordenar sus tipos de datos personalizados, etc.puede proporcionar una definición funcional de cómo pedir dos elementos.

De su ejemplo, su función determina el orden de dos números a y b. Javascript sort entonces utiliza su función diciendo ordenar cómo ordenar los elementos.

Resulta que mergesort es utilizado por Mozilla, mira: Javascript Array.sort implementation?

Answer 5

La función sort ordenará la matriz en una alphabetical sort order, incluso si se trata de números enteros; esa es la razón por la que su matriz se ordena así llamando al sort sin un parámetro.

sortOrder es una función de comparación que se utiliza para definir un nuevo orden de clasificación para la matriz; esta función devolverá

• 0, si a y b son del mismo valor
• un valor > 0, si a tiene un valor más grande que b
• un valor < 0, si a tiene un valor menor que b

En JavaScript, "1" - "2" volverá -1 , que es un número, y no una cadena más; mediante el uso de la función de comparación sortOrder en su matriz que tiene los números de envueltos en cadenas, usted está ordenando la matriz en un orden de clasificación numérica , lo que resulta en 1,5,10,25,40,100, y no en 1,10,100,25,40,5

Answer 6

Puede delegar la clasificación a su propia función de clasificación:

function sortnum(a,b) { 
return parseInt(a,10)-parseInt(b,10); 
} 
var n = ["10", "5", "40", "25", "100", "1"]; 
alert(n.sort(sortnum)); //=>["1", "5", "10", "25", "40", "100"] 

Answer 7

Para responder a su pregunta sobre cómo funciona la función de clasificación, se lo explicaré en detalle. Como se ha dicho en la mayoría de las respuestas aquí, al llamar solo al sort() en una matriz, se ordenará la matriz mediante cadenas. Convirtiendo tus enteros en cadenas también. ¡Blech!

Si piensa en sus elementos como caracteres en lugar de números, tiene sentido que se clasifique de esa manera. Una buena forma de ver esto es asignar letras a tus números.

//0 = a 
//1 = b 
//2 = c 
//4 = e 
//5 = f 
//These two arrays are treated the same because they're composed of strings. 
var nums = ["10", "5", "40", "25", "100", "1"]; 
var chars = ["ba", "f", "ea", "cf", "baa", "b"]; 

//Here we can see that sort() correctly sorted these strings. Looking at the 
//alphabetical characters we see that they are in the correct order. Looking 
//at our numbers in the same light, it makes sense that they are sorted 
//this way as well. After all, we did pass them as strings to our array. 
chars.sort(); //["b", "ba", "baa", "cf", "ea", "f"] 
nums.sort(); //["1", "10", "100", "25", "40", "5"] 

//The bad part of sort() comes in when our array is actually made up of numbers. 
var nums = [10, 5, 40, 25, 100, 1]; 
nums.sort(); //[1, 10, 100, 25, 40, 5] 

//As a result of the default sorting function converting numbers to strings 
//before sorting, we get an unwanted result. We can fix this by passing in our 
//own function as a parameter to sort(). 

Puede controlar cómo ordenar la matriz pasando su propia función como parámetro a la función sort(). Esto es bueno, pero a menos que sepa cómo funciona la función sort(), realmente no le servirá de nada.

sort() llamará a su función varias veces para reorganizar la matriz. Dependiendo de lo que devuelve su función, le dice a sort() qué hacer con los elementos en la matriz. Si se devuelve un número negativo o 0, no se produce ninguna reorganización. Si se devuelve un número positivo, los dos elementos cambian de lugar. sort() realiza un seguimiento de los números que ya ha probado, por lo que no termina probando los números más tarde después de haber cambiado los elementos. Si sort() reorganiza los artículos, retrocederá una posición y verá si ya probó estos dos elementos. Si no tiene, los probará. Si lo tiene, continuará sin ejecutar su función en ellos.

número de orden

Vamos a dar un ejemplo sencillo y que voy a caminar a través de él:

var arr = [50, 90, 1, 10, 2]; 

arr = arr.sort(function(current, next){ 
    //My comments get generated from here 
    return current - next; 
}); 

//1 : current = 50, next = 90 
// : current - next (50 - 90 = -40) 
// : Negative number means no re-arranging 
// : Array now looks like [50, 90, 1, 10, 2] 
// 
//2 : current = 90, next = 1 
// : current - next (90 - 1 = 89) 
// : Positive number means sort() will switch these positions in the array 
// : Array now looks like [50, 1, 90, 10, 2] 
// 
//If sort() didn't backtrack, the next check would be 90 and 10, switch those 
//positions, check 90 and 2, and switch again. Making the final array 
//[50, 1, 10, 2, 90], not sorted. But lucky for us, sort() does backtrack. 
// 
//3 : current = 50, next = 1 
// : current - next (50 - 1 = 49) 
// : Positive number means sort() will switch these positions in the array 
// : Array now looks like [1, 50, 90, 10, 2] 
// 
//If sort() wasn't smart, it would now check 50 and 90 again. What a waste! 
//But lucky for us again, sort() is smart and knows it already made this 
//check and will continue on. 
// 
//4 : current = 90, next = 10 
// : current - next (90 - 10 = 80) 
// : Positive number means sort() will switch these positions in the array 
// : Array now looks like [1, 50, 10, 90, 2] 
// 
//sort() backtracks one position and sees that it has not checked 50 and 10 
// 
//5 : current = 50, next = 10 
// : current - next (50 - 10 = 40) 
// : Positive number means sort() will switch these positions in the array 
// : Array now looks like [1, 10, 50, 90, 2] 
// 
//sort() backtracks one position and sees that it has not checked 1 and 10 
// 
//6 : current = 1, next = 10 
// : current - next (1 - 10 = -9) 
// : Negative number means no re-arranging 
// : Array now looks like [1, 10, 50, 90, 2] 
// 
//sort() remembers that it already checked 10 and 50 so it skips ahead 
//sort() remembers that it already checked 50 and 90 so it skips ahead 
// 
//7 : current = 90, next = 2 
// : current - next (90 - 2 = 88) 
// : Positive number means sort() will switch these positions in the array 
// : Array now looks like [1, 10, 50, 2, 90] 
// 
//sort() backtracks one position and sees that it has not checked 50 and 2 
// 
//8 : current = 50, next = 2 
// : current - next (50 - 2 = 48) 
// : Positive number means sort() will switch these positions in the array 
// : Array now looks like [1, 10, 2, 50, 90] 
// 
//sort() backtracks one position and sees that it has not checked 10 and 2 
// 
//9 : current = 10, next = 2 
// : current - next (10 - 2 = 8) 
// : Positive number means sort() will switch these positions in the array 
// : Array now looks like [1, 2, 10, 50, 90] 
// 
//sort() backtracks one position and sees that it has not checked 1 and 2 
// 
//10: current = 1, next = 2 
// : current - next (1 - 2 = -1) 
// : Negative number means no re-arranging 
// : Array now looks like [1, 2, 10, 50, 90] 
// 
//sort() remembers that it already checked 2 and 10 so it skips ahead 
//sort() remembers that it already checked 10 and 50 so it skips ahead 
//sort() remembers that it already checked 50 and 90 so it skips ahead 
//sort() has no more items to check so it returns the final array 
//which is [1, 2, 10, 50, 90] 

Si quería la matriz para ser ordenados en orden [90, 50, 10, 2, 1] descendente sólo puede cambiar la instrucción de retorno de return current - next; a return next - current; así:

var arr = [50, 90, 1, 10, 2]; 

arr = arr.sort(function(current, next){ 
    //My comments get generated from here 
    return next - current; 
}); 

//1 : current = 50, next = 90 
// : next - current (90 - 50 = 40) 
// : Positive number means sort() will switch these positions in the array 
// : Array now looks like [90, 50, 1, 10, 2] 
// 
//2 : current = 50, next = 1 
// : next - current (1 - 50 = -49) 
// : Negative number means no re-arranging 
// : Array now looks like [90, 50, 1, 10, 2] 
// 
//etc. 

no importa si la matriz es compo sed de "números de cadena" "5" o solo números 5 cuando usa su propia función para ordenar números. Porque cuando JavaScript hace matemática, trata los "números de cuerda" como números. es decir, "5" - "3" = 2

Ordenación de Cuerdas

Al ordenar las cadenas, se pueden comparar utilizando los operadores > y < (mayores-que y menor que). El operador mayor que ordena la cuerda por orden ascendente (A-Z, 1-9), y el operador menor que por orden descendente (Z-A, 9-1). Los diferentes navegadores utilizan diferentes algoritmos de clasificación, por lo que al ordenar por cadenas, debes asegurarte de que estás devolviendo 1 o -1, no verdadero o falso.

Por ejemplo, esto funciona en Chrome y FF, pero no IE:

var arr = ['banana', 'orange', 'apple', 'grape']; 

arr = arr.sort(function(current, next){ 
    return current > next; 
}); 

La manera de hacer que su algoritmo de ordenación funciona en todos los navegadores, utilice el operador ternario.

var arr = ['banana', 'orange', 'apple', 'grape']; 

arr = arr.sort(function(current, next){ 
    return current > next? 1: -1; 
}); 

Al cambiar la forma en que está la clasificación (por orden ascendente o descendente), además de cambiar los operadores, se puede mantener el mismo operador y cambiar las variables current y next como lo hicimos al ordenar números. O bien, dado que estamos utilizando el operador ternario, puede cambiar 1 y -1.

Ordenando Objetos

Aquí es un buen truco que pensé que me gustaría añadir aquí. Puede ordenar objetos si los agrega a una matriz y usa su clave para comparar. Aquí hay un ejemplo.

var arr = [ 
    {id: 2, name: 'Paul'}, 
    {id: 1, name: 'Pete'} 
]; 

//sort numerically 
arr = arr.sort(function(current, next){ 
    return current.id - next.id; 
}); 
//Array now looks like [{id: 1, name: 'Pete'}, {id: 2, name: 'Paul'}] 

//sort alphabetically 
arr = arr.sort(function(current, next){ 
    return current.name > next.name? 1: -1; 
}); 
//Array now looks like [{id: 2, name: 'Paul'}, {id: 1, name: 'Pete'}] 

Crónica

Para ordenar números
en orden ascendente (1, 2, 3 ...): function(a, b){return a - b;}
en fin (9, 8, 7 descendente .. .): function(a, b){return b - a;}

Para ordenar cadenas
en orden ascendente (A, B, C ...): function(a, b){return a > b? 1: -1;}
en orden descendente (Z, Y, X ...): function(a, b){return b > a? 1: -1;}

Para ordenar objetos añadirlos a una matriz,
continuación, ordenar por clave: function(a, b){return a.key - b.key;}