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.
https://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!
