Classificando em JavaScript: Não deveria retornar um booleano ser suficiente para uma function de comparação?

Eu sempre classifiquei com sucesso meus arrays assim (quando eu não queria a ordenação lexicográfica padrão):

var arr = […] // some numbers or so arr.sort(function(a, b) { return a > b; }); 

Agora, alguém me disse que isso estava errado e que eu precisaria return ab . Isso é verdade e, se sim, por quê? Eu testei minha function de comparação e funciona! Além disso, por que minha solução seria tão comum quando está errada?

TL; DR

Eu sempre classifiquei com sucesso meus arrays como este

Não, você não tem. E não percebeu isso. Um contra-exemplo rápido:

 > [1,1,0,2].sort(function(a, b){ return a>b }) Array [0, 1, 2, 1] // in Opera 12. Results may vary between sorting algorithm implementations 

porque?

Porque sua function de comparação retorna false (ou 0 , equivalentemente) mesmo quando b é maior que a . Mas 0 implica que os dois elementos são considerados iguais – e o algoritmo de sorting acredita nisso.

Explicação detalhada

Funções de comparação em JavaScript

Como funcionam as funções de comparação?

O método Array::sort pode ter uma function de comparação personalizada opcional como argumento. Essa function recebe dois argumentos (comumente chamados de b ) que deve ser comparada e deve retornar um número

  • > 0 quando a é considerado maior que b deve ser classificado depois
  • == 0 quando a é considerado igual a b e não importa o que vem primeiro
  • < 0 quando a é considerado menor que b e deve ser classificado antes dele

Se não retornar um número, o resultado será convertido em um número (o que é útil para booleanos). O número retornado não precisa ser exatamente -1 ou 0 ou 1 (embora normalmente seja).

Ordenação consistente

Para ser consistente, a function de comparação precisaria preencher a equação

 comp(a, b) == -1 * comp(b, a) // or, if values other than -1, 0 and 1 are considered: comp(a, b) * comp(b, a) < = 0 

Se esse requisito for quebrado, a sorting se comportará como indefinida.

Citando a especificação ES5.1 na sort (mesma coisa na especificação ES6 ):

Se comparefn é […] não uma function de comparação consistente para os elementos dessa matriz, o comportamento de ordenação é definido pela implementação.

Um comparefn function é uma function de comparação consistente para um conjunto de valores S se todos os requisitos abaixo forem atendidos para todos os valores a , b e c (possivelmente o mesmo valor) no conjunto S : A notação a significa comparefn(a,b) < 0 ; a =CF b significa comparefn(a,b) = 0 (de qualquer sinal); e a >CF b significa comparefn(a,b) > 0 .

Chamar comparefn(a,b) sempre retorna o mesmo valor v quando é dado um par específico de valores a e b como seus dois argumentos. Além disso, Type(v) é Number e v não é NaN . Note que isto implica que exatamente um dos a , a =CF b e a >CF b será verdadeiro para um dado par de a e b .

  • Chamar comparefn(a,b) não modifica o object this.
  • a =CF a ( reflexividade )
  • Se a =CF b , então b =CF a ( simetria )
  • Se a =CF b e b =CF c , então a =CF c ( transitividade de =CF )
  • Se a e b , então a (transitividade de )
  • Se a >CF b e b >CF c , então a >CF c (transitividade de >CF )

NOTA: As condições acima são necessárias e suficientes para assegurar que o comparefn divide o conjunto S em classs de equivalência e que estas classs de equivalência são totalmente ordenadas.

O que isso significa? Por que eu deveria me importar?

Um algoritmo de sorting precisa comparar itens do array entre si. Para fazer um trabalho bom e eficiente, não é necessário comparar cada item com outro, mas precisa ser capaz de raciocinar sobre o pedido deles. Para que isso funcione bem, existem algumas regras que uma function de comparação personalizada precisa obedecer. Um trivial é que um item a é igual a ele mesmo ( compare(a, a) == 0 ) - esse é o primeiro item da lista acima (reflexividade). Sim, isso é um pouco matemático, mas paga bem.

O mais importante é a transitividade. Ele diz que quando o algoritmo comparou dois valores b , e também b com c , e descobriu pela aplicação da function de comparação que, por exemplo, a = b e b < c , então pode-se esperar que a < c também seja . Isso parece apenas lógico e é necessário para uma ordenação consistente e bem definida.

Mas a sua function de comparação falha nisso . Vamos ver este exemplo:

  function compare(a, b) { return Number(a > b); } compare(0, 2) == 0 // ah, 2 and 0 are equal compare(1, 0) == 1 // ah, 1 is larger than 0 // let's conclude: 1 is also larger than 2 

Ooops E é por isso que um algoritmo de sorting pode falhar (na especificação, isso é " comportamento dependente da implementação " - isto é, resultados imprevisíveis) quando é invocado com uma function de comparação que não é consistente.

Por que a solução errada é tão comum?

Como em muitos outros idiomas, existem algoritmos de ordenação que não esperam uma comparação a três, mas apenas um operador booleano menor que o. C ++ std::sort é um bom exemplo disso. Ele será simplesmente aplicado duas vezes com argumentos trocados se uma igualdade precisar ser determinada. Evidentemente, isso pode ser mais eficiente e menos propenso a erros, mas precisa de mais chamadas para a function de comparação se o operador não puder ser embutido.

CounterExamples

Eu testei minha function de comparação e funciona!

Apenas por pura sorte, se você tentou algum exemplo random. Ou porque sua suíte de testes está com defeito - incorreta e / ou incompleta.

Aqui está o pequeno script que usei para encontrar o contra-exemplo mínimo acima:

 function perms(n, i, arr, cb) { // calls callback with all possible arrays of length n if (i >= n) return cb(arr); for (var j=0; jb }).toString() != a.slice().sort(function(a,b){ return ab }).toString() ) // you can also console.log() all of them, but remove the loop! throw a.toString(); }); 

Qual function de comparação está correta?

Não use nenhuma function de comparação quando quiser uma sorting lexicográfica. Itens na matriz serão estipulados se necessário.

Uma function de comparação genérica que funciona como os operadores relacionais pode ser implementada como

 function(a, b) { if (a > b) return 1; if (a < b) return -1; /* else */ return 0; } 

Com alguns truques, isso pode ser diminuído para a function(a,b){return +(a>b)||-(a equivalente function(a,b){return +(a>b)||-(a .

Para números , você pode simplesmente retornar a diferença, que obedece a todas as leis acima:

 function(a, b) { return a - b; // but make sure only numbers are passed (to avoid NaN) } 

Se você quiser ordenar de forma inversa, basta pegar o apropriado e trocar a com b .

Se você quiser ordenar tipos compostos (objects etc), substitua cada a e cada b por um access das propriedades em questão, ou uma chamada de método ou o que você deseja classificar.

A function sort espera uma function que espera dois argumentos b , e retorna:

  • Um número negativo se vier antes b
  • Um número positivo se vier depois de b
  • Zero se ordem relativa de aeb não importa

Para ordenar números em ordem ascendente, return a - b produzirá os valores de retorno corretos; por exemplo:

 ab ret 1 2 -1 3 2 1 2 2 0 

Por outro lado, return a > b produz os seguintes valores de retorno:

 ab ret implied 1 2 false 0 3 2 true 1 2 2 false 0 

No exemplo acima, a function de sorting é informada de que 1 e 2 são iguais (e colocar 1 antes de 2 ou 2 antes de 1 não importa). Isso produzirá resultado incorreto, por exemplo (no Chrome 49):

 [5, 8, 7, 1, 2, 3, 4, 6, 9, 10, 11, 12, 13].sort(function(a, b) { return a > b; }); // [4, 5, 3, 1, 2, 6, 7, 8, 9, 10, 11, 12, 13]