Algoritmos com JavaScript II: aprofundando em algoritmos de ordenação e busca

Dividir para conquistar - Apresentação

Olá. Boas vindas ao curso de algoritmos com JavaScript. Nesse curso vamos continuar de onde paramos no curso anterior de algoritmos, continuando a trabalhar com alguns exemplos de algoritmos de ordenação e de busca.

Esse curso está voltado para quem está começando em programação, escolheu o JavaScript como linguagem de entrada e já teve contato com os fundamentos, como tipos de dado, array, objetos, funções etc.

Lembrando que vamos continuar direto de onde paramos, então é interessante que você tenha feito o curso anterior de algoritmos com JavaScript, que está listado na página do curso.

Onde começamos e até onde vamos? Vamos continuar trabalhando com algoritmos de ordenação, veremos mais dois exemplos. E dessa vez veremos exemplos um pouco mais complexos, porém, mais utilizados na vida real, quando precisamos ordenar grandes quantidades de dados.

A mesma coisa com algoritmos de busca: vamos olhar mais um exemplo de algoritmo, que é também mais eficiente do que os vistos anteriormente, mas vamos numa progressão de complexidade, para entendermos bem como funcionam, de onde saem os conceitos que utilizamos para desenvolver os algoritmos.

Continuando com o teste de mesa para compreender melhor os algoritmos, o que exatamente está guardando uma variável, em determinada parte do processamento? Para isso vamos continuar simulando e fazendo testes de mesa para entender bem todo o passo a passo de cada um dos algoritmos que vamos trabalhar durante o curso.

E também, seguindo com análise de complexidade. Já temos uma ideia de como funciona a análise de complexidade, de como descobrimos o quão complexo é, o quanto um algoritmo afeta a performance de um programa. E vamos fazer a análise de complexidade dos algoritmos que serão trabalhados durante o curso.

Nesse curso continuamos trabalhando firme com partes fundamentais do JavaScript, aquilo que falamos anteriormente, como tipos de dados, funções, arrays principalmente. Mas não vamos explicar em detalhe o funcionamento de cada uma dessas partes.

Então você vai aproveitar melhor se já tiver um contato legal com esses fundamentos e, novamente, se já tiver passado pelo curso anterior.

Lembrando que nestes cursos não falamos sobre assuntos específicos de front-end, porém, mesmo se você trabalhar com front-end, você consegue aproveitar os conceitos da mesma forma.

Existem vários algoritmos que já foram desenvolvidos e estudados para resolver os mais diversos problemas computacionais que vemos no dia a dia.

Depois desse curso você consegue estudar mais e melhor por conta própria, entender todos os outros tipos de algoritmo, não só de busca e de ordenação, que são os que estamos vendo, mas vários outros e entender as complexidades de cada um, onde e como eles são utilizados.

Eu sou a Ju Amoasei, então vamos começar.

Dividir para conquistar - Misturando listas

Lembrando do que vimos no curso anterior de algoritmos com JavaScript, começamos com uma livraria, uma lista de livros. Fomos ordenando essa lista de livros, buscando valores específicos, ordenando do menor valor para o maior.

E trabalhamos basicamente com dois tipos de ordenação, que chamamos de selection sort e insertion sort. Ambos esses algoritmos de ordenação trabalhavam percorrendo a lista de livros, ou de qualquer coisa que passássemos, e verificando se o elemento está no lugar certo, se um elemento é menor do que outro, trocando de lugar etc.

Também fizemos o que chamamos de análise assintótica do nível de complexidade desses algoritmos. Fizemos planilhas e tabelas para ver como esses algoritmos cresciam em complexidade e adicionavam quantidade de operações que o computador teria que fazer.

Vamos continuar trabalhando nesse sentido. Também continuamos com a ideia de lista de livros de uma livraria. Só que vamos tentar pensar em outras formas de ordenar, outros algoritmos de ordenação para listas, pensando em algumas abordagens diferentes.

Vamos começar pensando, por exemplo, em dividir o problema. Às vezes temos uma quantidade muito grande de coisas para ordenar na mão, e dividimos esse trabalho entre várias pessoas, cada uma ordenando um pouco, sejam pilhas de provas com notas ou cartas de um jogo etc.

Nós vamos trabalhar com o mesmo modelo de listas, pensando que minha livraria recebeu uma lista de catálogo da editora Folha e uma lista de catálogo da editora Galho. Elas já estão ordenadas, cada editora ordenou por preço seus livros.

Só que a minha livraria vai vender das duas editoras, então temos que juntar essas duas listas em uma só. Pensando na nossa cabeça, como resolveríamos isso?

Nós podemos trabalhar de duas formas. Podemos pensar em pegar uma das listas, por exemplo, vou pegar a lista da editora Folha, que chamarei de lista 1, e jogo numa lista final. Se uma lista tem 5 elementos e a outra tem 6, então eu penso que minha lista final tem 11 elementos.

Então pego uma lista de 11 elementos, pego uma das listas pequenas, jogo no lugar e parto para a outra.

Na segunda lista eu tenho que o primeiro elemento custa R$ 20. Vou, na lista final, ter um espaço entre o elemento de 15 e o de 25, então eu empurro entre 15 e 25 e coloco o de 20 no lugar. É um pouco parecido com o insertion sort que trabalhamos no curso anterior. Essa é uma forma de fazer.

Mas tem outra forma de fazer também. Já que teremos uma lista final, o que podemos fazer é pegar um elemento por vez de cada lista.

Lembrando que são duas listas ordenadas, então pego o primeiro elemento da lista 1 e da lista 2, comparo e vejo qual é o menor.

Se fizermos dessa forma, o primeiro elemento da lista 1 custa 15. O primeiro elemento da lista 2 custa 20. Então eu pego o elemento de 15 reais da lista 1 e coloco como primeiro elemento da lista final.

Agora a minha lista 1 não tem mais o primeiro elemento. O próximo elemento que eu vou trabalhar é o elemento 2. E na lista atual a mesma coisa. A posição de primeiro elemento já foi ocupada. Então agora vamos ver qual é o segundo elemento.

No segundo elemento da lista 1 eu tenho R$ 25, que é o livro de JavaScript. E na lista 2 tenho o Python, de R$ 20. 20 é menor do que 25, o Python é mais barato. Então a segunda posição na lista final ordenada será ocupada pelo produto de R$ 20, o Python.

A posição atual da minha lista final muda também, agora vamos passar para a próxima. E é a mesma coisa na lista 2, que foi a única lista de onde tiramos o elemento anterior.

Então continuando, agora na lista 1 o elemento atual que estamos trabalhando ainda é o JavaScript, que custa R$25. Mas na lista 2, agora o elemento da vez é um livro de Rust, que custa R$ 22. 22 é menor que 25, vamos puxar o 22 para a próxima posição da lista final.

Andamos com a posição da lista final e andamos com a posição atual da lista 2 para o próximo elemento. E agora vamos comparar JavaScript, que era o maior valor na operação anterior, com um livro de Ruby que custa 28. Agora JavaScript é menor, 25 é menor que 28. Então a próxima posição quem ocupa é JavaScript, que custa 25.

Passamos somente a lista 1, que foi a que trabalhamos, para a próxima posição. Agora comparamos Java, que custa 30, com Ruby, que custa 28. Agora Ruby é mais barato, então puxamos somente esse elemento da lista 2 para a lista final, e andamos somente com a lista 2 e com a lista final.

Agora temos que comparar Java, que custa 30, com C#, que custa 33. Então Java, de 30, é o próximo elemento mais barato. Vamos andar com a posição atual da lista final e da lista 1, que é onde estava o Java.

Agora nossa comparação é entre Go, que custa 45, e C# que custa 33. 33 é mais barato que 45, então andamos a lista 2 para a próxima posição e a lista atual também.

Nossa comparação agora é entre Go, de 45, e C++, ou CPP. Eu chamo de CPP porque eu acho mais fácil de falar, mas é a mesma coisa.

Comparamos o livro de CPP, que custa 35, com um livro de Go, que custa 45. CPP é mais barato, então o puxamos para a próxima posição, e a próxima posição da lista final.

Agora nossa lista 1 tem Go 45, que continua sendo o elemento da vez, e a lista 2 com o Scala de 40. 40 ainda é mais barato que 45, então puxamos o Scala da lista 2 para a posição atual da lista final.

Agora temos o elemento Go, que é o elemento da vez da lista 1. Só que a lista 2, que tinha 6 elementos, acabou, não tem mais nada. Sobraram dois elementos na lista 1, um de 45 e outro de 50.

Só que já sabemos que como isso já estava ordenado, não tem mais nada para ordenar. Só temos que puxar os dois elementos que sobraram da lista 1 para os dois últimos lugares da minha lista final de 11 elementos.

E agora está tudo ordenado. Então fomos comparando, puxando um por vez. Tínhamos duas listas ordenadas e agora temos uma lista que misturou as duas. Pegamos duas partes menores que já estavam ordenadas e juntamos em uma lista grande ordenada.

Esse tipo de simulação que fazemos em código já vimos que nos ajuda bastante a entender como funciona o fluxo, os passos de um algoritmo, por exemplo, de ordenação, antes de tentarmos fazer o código dele.

Então o que faremos agora, antes de passar para o código, é evoluir um pouco essa simulação, transformá-la em algo um pouco mais parecido com um teste de mesa e então entendemos bem como vai funcionar esse lance de ficar comparando e pulando de lista em lista para juntar depois tudo numa lista grande. Vamos fazer isso em seguida.

Dividir para conquistar - Testando o algoritmo

Já desenvolvemos o básico de como vai funcionar esse algoritmo de ordenação que criamos e pensamos para juntar duas listas ordenadas em uma só.

Mas antes de passar para o código, vamos fazer um teste mais elaborado, mais parecido com os testes de mesa, que já fizemos no curso passado.

Agora temos variáveis para ir controlando o que acontece em cada parte desse fluxo do algoritmo, para cada lista que ele vai percorrer, juntar em uma lista só etc.

Eu já criei algumas variáveis. Criei uma variável “atualLista1” para controlar o andamento da posição atual da lista 1, da editora Folha. E outra variável para a editora Galho, que eu chamei de “atualLista2”, ambas começando com 0, que é a primeira posição do array.

Então começamos pela primeira posição de cada um dos arrays, fazendo as comparações. O comprimento do array da lista 1 é 5, o comprimento do array da lista 2 é 6, então teremos no final um array de 11 posições.

E criei também uma variável que eu chamei de “atualFinal”, também começando com 0, que é a variável que vai controlar a posição atual do array final, da lista final.

Agora percorremos o mesmo caminho, fazendo as comparações. Começando em “atualLista1”, na posição 0 e “atualLista2” na posição 0. Eu tenho PHP de 15 e Python de 20. Vou puxar PHP para a lista atual.

A posição atual da lista 1 passa para 1, a posição atual da lista final passa para 1 também. Lembrando que estamos trabalhando com arrays começando com 0, por isso que todas as nossas variáveis estão começando com 0 também.

A “atualLista2” não mexe, porque não tiramos nada dessa lista. E é o mesmo processo: na lista 1 temos 25 e na lista 2 20.

O livro de 20 da lista 2 vai para a lista final. Na lista final agora a próxima posição é o 2, e na lista 2 a próxima posição é 1.

A próxima comparação é entre 25 na lista 1 e 22 na lista 2. Movemos novamente o elemento da lista 2 para baixo. Agora a posição atual da lista 2 é 2 e a posição atual da lista final é 3.

Continuando o processo, agora nossa comparação é entre 25 da lista 1 com 28 da lista 2. Desce o 25 da lista 1. Agora a posição atual da lista 1 é 2, e a posição atual da lista final é 4.

Continuando, agora nossa comparação é entre 30 na lista 1 e 28 na lista 2. Desce o 28 da lista 2. A posição atual da lista 2 agora é 3, e a posição atual da lista final é 5.

Na lista final a posição 0 é do PHP, que custa 15, a posição 1 é de Python, que custa 20, a posição 2 é de Rust, que custa 22, a posição 3 é de JavaScript, que custa 25 e a posição 4 é de Ruby, que custa 28. Então agora passamos para a posição 5.

Agora comparamos 30 da lista 1 com 33 da lista 2. Passamos o 30 da lista 1 para baixo. A lista atual vai para o índice 6. A lista 1 movimenta de novo e vai para o índice 3.

Mais uma comparação, agora entre 45 na lista 1 com 33 na lista 2. Desce o 33 da lista 2. Então a posição atual agora da lista final vai para 7 e a posição atual da lista 2 vai para 4.

Continuando, agora eu tenho 45 na lista 1 e 35 na lista 2. Eu desço 35 da lista 2. A posição atual da lista final agora é 8. E a posição atual da lista 2 agora é 5.

Continuando, agora temos 45 na lista 1 e 40 na lista 2. Desce o 40 da lista 2. A posição atual da lista final passa a ser 9. A posição atual da lista 2 passa a ser 6.

Só que o comprimento do array da lista 2 é igual a 6, então o comprimento é igual ao índice atual. Lembrando do for clássico, não temos mais nada para fazer nessa lista.

Mas ainda tem elementos na lista 1. Lembrando que nesse loop estamos pensando em fazer um por um. Agora temos na lista 1 o 45, não tem mais nada na lista 2. Descemos o 45 da lista 1.

Agora a lista atual vai para a posição 10 e a lista 1 continua andando, e agora está na 4. Ainda é menor do que o comprimento da lista 1, que é 5, então continuamos nela.

Só tem mais um item, que é o de 50. Vamos descê-lo para a lista final. A posição atual da lista final agora é 11, que não é mais menor do que o tamanho da lista final.

E a mesma coisa se aplica para a lista 1. Agora a posição atual da lista 1 é 5, que não é menor do que o comprimento do array. E acaba o nosso processamento.

Então agora já temos algo mais parecido com o que podemos aplicar no código, inclusive o funcionamento de como será esse fluxo, esse laço de repetição.

Vamos percorrer duas listas, teremos que manejar a posição atual de cada uma das listas pelo índice do array, e comparando para ver de quanto em quanto ele vai andando e que horas temos que parar com esse processamento.

Agora sim vamos escrever o código que já temos na cabeça como vai funcionar em JavaScript.

Sobre o curso Algoritmos com JavaScript II: aprofundando em algoritmos de ordenação e busca

O curso Algoritmos com JavaScript II: aprofundando em algoritmos de ordenação e busca possui 173 minutos de vídeos, em um total de 49 atividades. Gostou? Conheça nossos outros cursos de Node.JS em Programação, ou leia nossos artigos de Programação.

Matricule-se e comece a estudar com a gente hoje! Conheça outros tópicos abordados durante o curso:

• Dividir para conquistar
• Merge Sort
• Quick Sort
• Busca binária
• Análise dos algoritmos