Estava eu às cinco horas da manhã de um domingo curtindo o melhor programa que esse horário pode proporcionar: Estudar algorítmos.
O autor do livro frisa na introdução que algoritmos são tão importantes quanto um bom hardware, pois a utilização de um procedimento ineficaz poderia tornar o sistema tão ou mais lento quanto usar equipamentos ultrapassados.
Estou ainda no início do livro, estudando conceitos básicos e sendo apresentados aos algorítmos mais elementares. O primeiros deles é o algortmo de ordenação.
Resolvi fazer um teste utilizando dois algoritmos de ordenação aprendizos no livro: Insertion-Sort e Merge-Sort.
O algoritmo Insertion Sort se assemelha muito a como um humano faria caso fosse incumbido da tarefa de ordenar uma lista: Seleciona-se um elemento da lista e compara com os demais e a partir daí cria-se uma nova lista inserindo(insertion) os elementos já ordenados.
Esse algorimto é mais adequado para humanos, que podemos rapidamente comparar com os elementos adjacentes onde melhor colocar o elemento destacado. Porém para computadores, é muito pouco eficaz, pois o computador vai sempre avaliar todas as peças antes de encaixar o elemento no seu lugar devido.
O Merge Sort por sua vez é mais adequado para computadores. Ele agrupa(merge) os elementos e ordena grupo a grupo, dobrando o tamanho dos grupos em recursão até só restem dois grupos enormes para ser ordenados.
Resolvi codificar esses dois algoritmos em Javascript e testar a eficácia de ambos.
E o resultado é o que vocês podem ver a seguir:
Até os 16k a diferença é negligenciável, mas a partir daí a diferença começa a ficar avassaladora até o ponto em que o Merge-Sort conlcui a tarefa 46x mais rápido que o Insertion-Sort. Eu testei até um pouco mais de 1 milhão de elementos, mas imaginem se a Riot Games, empresa do League of Legends, utilizasse o Insertion-Sort para ordenar a sua lista de mais de 117 milhões de jogadores?
