Algoritmos de ordenação e o seu JavaScript

Insert sort, selection sort, quick sort, etc. Legal, mas onde esses algoritmos são aplicados de fato no seu JavaScript?

por Marcelo Galvão 04/09/2017 Comentários


gif insertion sort — Wikipedia

Insert sort, selection sort, quick sort, etc. Legal, mas onde esses algoritmos são aplicados de fato no seu JavaScript?

Enquanto estudava estrutura de dados e afins, me deparei com esses conceitos de programação e meu questionamento ficou sem resposta. Eu queria ver de fato a implementação de uma linguagem de programação usando esses conceitos, ué. haha

Esses dias precisei ordenar um array em JavaScript e me deparei com o método sort() e fui estudá-lo. Afinal, como algumas coisas em JS, ele nem sempre funciona bem como esperado #aiMeuJavascript .

Sort()

Esse método classifica os valores como string e os ordena em ordem ascendente. Ou seja, se seu array for de valores numéricos ele não terá a ordenação que você deseja. Pois o valor será interpretado como uma string e aí sim ordenado.

var ar = [40, 10, 101, 20];
ar.sort();
// [10, 101, 20, 40]

Solução

// passe uma função de comparação como parâmetro

var ar = [40, 10, 101, 20];
ar.sort( function(a, b){
   return a — b;
});
// [10, 20, 40, 101]

/*
Observe que isso também é útil para ordenar um array de objetos. Ordenando 
com base em um valor numérico de um determinado atributo. (exe.: idade, peso).
*/

Por trás do Sort()

Durante o estudo resolvi observar os loops de comparação e percebi algo semelhante a grandeza encontrada no insertion sort (nesse caso, 5x). Que não é o melhor algoritmo, mas trabalha bem com pequenos vetores numéricos.

Graças ao mundo open source podemos dar uma olhada no código fonte de algumas engines JavaScript utilizada nos navegadores, escritas em C/C++.

V8

Olhando o código da engine JavaScript V8 — utilizada no Chrome — podemos observar menções ao quick sort (linha 768), insertion sort (linha 734), entre outros algoritmos e suas implementações :)

https://github.com/v8/v8/blob/fe598532ec1317e8b85343133be9fb708e07bd2e/src/js/array.js#L768

E o seguinte comentário:

For short (length <= 10) arrays, insertion sort is used for efficiency.

WebKit

No WebKit podemos ver sua implementação em C++ para os tratamentos com array.

https://trac.webkit.org/browser/trunk/Source/JavaScriptCore/runtime/JSArray.cpp?rev=138530#L972

SpiderMonkey

No SpiderMonkey, engine JavaScript utilizada no Firefox.

https://hg.mozilla.org/mozilla-central/file/28be8df0deb7/js/src/jsarray.cpp

C++

No código fonte do navegador, como esperado, muitas vezes simplesmente chama-se a implementação do próprio C++, por exemplo o quick sort.

http://en.cppreference.com/w/cpp/algorithm/qsort

Discussão antiga

Quando pesquisava sobre o Firefox encontrei esse thread aberta a 14 anos atrás (!) onde o pessoal discute sobre o assunto, inclusive o próprio **Brendan Eich, **aparentemente ainda com cara de jovem 😛
https://bugzilla.mozilla.org/show_bug.cgi?id=224128#c8
Na ocasião, ele explica porque usa quick sort.

Conclusão

Existem vários algoritmos de busca e ordenação. Cada um com sua importância, particularidade e propósito. Seja para números, string, etc. É interessante ver casos como o do V8, que faz um tratamento e usa o mais adequado a necessidade. Mas o mais interessante mesmo foi ver que eles realmente estão lá :P

Ps.: Não entrei no detalhe das implementações em C++ porque não tenho conhecimento na linguagem. Se você possui e tem algo a acrescentar, por favor, sinta-se convidado!