Classificação em JavaScript: toda function de comparação deve ter uma instrução “return 0”?

Recentemente li muitas respostas sobre sorting em JavaScript e muitas vezes me deparo com uma function de comparação que se parece com isso:

array.sort(function(a,b){ a > b ? 1 : -1; }); 

Portanto, é uma function de comparação que retorna 1 se a for maior que b e -1 se a for menor que OR EQUAL TO b . Conforme descrito no MDN ( link ), uma function de comparação também pode retornar zero, para garantir que a posição relativa de dois itens permaneça inalterada:

Se compareFunction (a, b) retornar 0, deixe a e b inalterados em relação um ao outro, mas classificados em relação a todos os diferentes elementos.

Então, os exemplos oficiais parecem mais com isso:

 function compare(a, b) { if (a  b) return 1; return 0; } 

E, de fato, adicionando uma instrução return 0 , o algoritmo de sorting geralmente precisa de menos iterações e é executado mais rapidamente no total ( JSPerf ).

Então eu queria saber se há alguma vantagem em omitir uma declaração de return 0 .

Eu percebi que no MDN, também diz:

Nota: o padrão ECMAscript não garante este comportamento e, portanto, nem todos os navegadores (por exemplo, versões do Mozilla que remontam a pelo menos 2003) respeitam isso.

referindo-se ao comportamento, que b devem permanecer inalterados se 0 for retornado. Então, talvez, ao retornar 0, tenhamos uma matriz ordenada ligeiramente diferente em diferentes navegadores? Isso poderia ser uma razão? E existem outras boas razões para não retornar zero?

Então eu queria saber se há alguma vantagem em omitir uma declaração de retorno 0.

Menos letras para digitar. E pode ser um pouco mais rápido devido a uma comparação omitida. Todos os outros efeitos são desvantagens .

Eu percebi que no MDN, também diz:

Nota: o padrão ECMAscript não garante este comportamento e, portanto, nem todos os navegadores (por exemplo, versões do Mozilla que remontam a pelo menos 2003) respeitam isso.

referindo-se ao comportamento, que aeb devem permanecer inalterados se 0 for retornado.

Que a posição de a e b pode permanecer inalterada é apenas o requisito para uma sorting estável . Este não é um comportamento especificado e alguns navegadores implementaram um algoritmo de sorting não estável.

No entanto, a finalidade real de retornar zero é que nem a é classificado antes de b (como se fosse menor que 0) nem que b é classificado antes de a (como se fosse maior que 0) – basicamente quando a é igual a b . Este é um must-have para uma comparação , e todos os algoritmos de ordenação obedecem a ele.

Para produzir uma ordenação válida e satisfatória (matematicamente: dividir os itens em classs de equivalência totalmente ordenadas ), uma comparação deve ter certas propriedades. Eles estão listados na especificação para sort como requisitos para uma ” function de comparação consistente “.

O mais proeminente é a reflexividade, exigindo que um item a seja igual a a (em si). Outra maneira de dizer isso é:

compare(a, a) deve sempre retornar 0

O que acontece quando uma function de comparação não satisfaz isto (como a que você tropeçou obviamente faz)?

A especificação diz

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

o que basicamente significa: se você fornecer uma function de comparação inválida, a matriz provavelmente não será classificada corretamente. Ele pode ser aleatoriamente permutado ou a chamada de sort pode nem ser encerrada.

Então, talvez, ao retornar 0, tenhamos uma matriz ordenada ligeiramente diferente em diferentes navegadores? Isso poderia ser uma razão?

Não, retornando 0, você obtém uma matriz ordenada corretamente nos navegadores (o que pode ser diferente devido à sorting instável). A razão é que, ao não retornar 0, você obtém arrays permutados ligeiramente diferentes (se houver), talvez até produzindo o resultado esperado, mas geralmente de maneira mais complicada.

Então, o que poderia acontecer se você não retornasse 0 para itens equivalentes? Algumas implementações não têm problemas com isso, já que elas nunca comparam um item a si mesmo (mesmo que aparente em múltiplas posições na matriz) – pode-se otimizar isso e omitir a dispendiosa chamada à function de comparação quando já se sabe que o resultado deve seja 0.

O outro extremo seria um loop que nunca termina. Supondo que você tivesse dois itens equivalentes um após o outro, você compararia o último com o primeiro e perceberia que tinha que trocá-los. Testando novamente, o último ainda seria menor que o anterior e você teria que trocá-los novamente. E assim por diante…

No entanto, um algoritmo eficiente geralmente não testa os itens já comparados novamente e, normalmente, a implementação será encerrada. Ainda assim, pode fazer mais ou menos swaps que na verdade foram desnecessários e, portanto, levarão mais tempo do que com uma function de comparação consistente.

E existem outras boas razões para não retornar zero?

Sendo preguiçoso e esperando que o array não contenha duplicatas.

Um método de comparação deve obedecer ao contrato

 Math.sign(compare(a, b)) = -Math.sign(compare(b, a)) 

Se você retornar uma resposta diferente de zero quando a == b, esse contrato será violado.