Algoritmos de ordenação e o seu JavaScript

Marcelo Galvão
Aug 29, 2017 · 3 min read

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

gif insertion sort — Wikipedia

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

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!

Tableless

Um lugar para ler e discutir sobre desenvolvimento, design, web semântica, back-end e outros assuntos relacionados a web. Se você quiser publicar artigos conosco, envie um email: medium[at]tableless.com.br ou *clique no link* http://bit.ly/escreva-tableless-medium

Marcelo Galvão

Written by

Fascinado por algoritmos. Desenvolvedor web na Accenture Brasil.

Tableless

Tableless

Um lugar para ler e discutir sobre desenvolvimento, design, web semântica, back-end e outros assuntos relacionados a web. Se você quiser publicar artigos conosco, envie um email: medium[at]tableless.com.br ou *clique no link* http://bit.ly/escreva-tableless-medium

More From Medium

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade