JavaScript I: algoritmos de ordenação

Pensando em algoritmos - Apresentação

Olá, boas-vindas ao curso de algoritmos com JavaScript.

Nesse curso, nós vamos conversar sobre o que são algoritmos e por que o estudo de algoritmos é tão importante em programação. Vamos começar analisando alguns problemas comuns de programação e de que forma podemos resolvê-los com algoritmos, algoritmos diversos.

Esse curso está voltado para quem está começando do começo em programação e escolheu o JavaScript como linguagem, mas que já teve contato com os fundamentos do JavaScript: o que são dados primitivos, número, string, booleano, arrays, objetos e funções.

Onde nós começamos e até onde vamos? Vamos começar traduzindo problemas, às vezes problemas do dia a dia mesmo, que resolvemos de cabeça, como falamos.

E vamos traduzir a resolução desses problemas para o passo a passo de um algoritmo. Vamos escrever esses algoritmos usando funções e métodos do JavaScript. Vamos transcrever esses passos, esses fluxos para código.

Juntar algoritmos. Às vezes, nós precisamos, para resolver problemas, trabalhar com mais de um algoritmo de uma vez. Vamos ver como usamos isso, como isso funciona no código.

E testes de mesa. Às vezes, nós sabemos que um bloco de código está funcionando, mas não entendemos totalmente de que forma isso está ocorrendo. Por exemplo, quando usamos um algoritmo pronto – vamos ver como isso funciona durante o curso – temos lá um código que resolver um problema, mas o que está acontecendo dentro desse código?

O que está guardado nas variáveis, o que faz cada linha? Então, os testes de mesa nos ajudam a seguir o fluxo de um algoritmo, o fluxo de um bloco de código linha por linha, variável por variável, e nós conseguimos entender exatamente todos os passos. Então, vamos fazer alguns testes de mesa.

Vamos comparar algoritmos também. Como sabemos se um algoritmo funciona bem para o nosso caso e o que é funcionar bem, quando falamos de algoritmos.

Análise de complexidade porque, pensando que algoritmos executam instruções, instruções de código, como conseguimos saber quão complexo um algoritmo pode se tornar baseado na quantidade de dados que temos para trabalhar com ele?

Então, tenho muitos dados, tenho uma lista com muitos livros, tenho vários candidatos de um vestibular, como eu uso algoritmos de busca para isso? Como uso um algoritmo de ordenação?

E o quão complexo que o código desse algoritmo, que as instruções podem se tornar em termos de processamento, de acordo com a quantidade de dados que trabalhamos? Vamos ver como isso funciona também.

Nesse curso, vamos trabalhar firme com algumas partes fundamentais do JavaScript. Tipos de dados, variáveis, funções, arrays e objetos. Mas não vamos parar para explicar em detalhes o funcionamento, o conceito por trás de cada uma dessas partes fundamentais.

Você vai aproveitar melhor o curso se já tiver feito os cursos anteriores sobre fundamentos do JavaScript ou se você já tiver estudado sobre esses assuntos.

Lembrando que, nesse curso, nós não vamos falar sobre assuntos específicos de front-end, mas tudo que vamos ver aqui você pode abstrair e aproveitar os conceitos da mesma forma.

Depois desse curso, você pode estudar mais algoritmos por conta própria, entender como diversos algoritmos funcionam para diversos problemas.

Quais as complexidades de cada um e como você consegue, por exemplo, pegar o conceito de um algoritmo escrito em pseudocódigo e passá-lo para JavaScript para você conseguir usar em um projeto ou testar e entender melhor como ele funciona.

Eu sou a Ju Amoasei e vamos começar.

Pensando em algoritmos - Nosso primeiro problema

Boas-vindas ao curso de algoritmos com JavaScript. Vamos começar vendo qual é o nosso problema, o que nós vamos trabalhar nesse curso.

Vamos supor que nós ganhamos um vale-presente em uma livraria de X, digamos, cinquenta reais, cem reais, e queremos ganhar esse vale-presente em livros de programação.

Nós entramos no site da livraria, procuramos por livro de programação, e recebemos algumas opções. Só que o site da livraria trouxe para nós essas opções – um livro de JavaScript (25,00), um livro de PHP (15,00), um livro de Java (30,00), Elixir (50,00), Go (45,00) e Python (20,00) – que não estão em nenhuma ordem particular que consigamos ver.

Não está em ordem alfabética e não está em ordem de preço, os preços estão misturados, os mais caros com mais baratos etc. Então, qual é o problema que nós temos? Quando temos um vale-presente, normalmente nós queremos fazer o melhor uso possível dele.

Então, o que vale mais a pena? Tenho um vale de cinquenta reais, comprar cinco livros de dez reais ou comprar dois livros de vinte e cinco reais? Para conseguirmos fazer isso, temos que saber quais são os livros mais baratos, como eu consigo somar etc.

Então, temos aqui a nossa busca de livros que trouxe uma lista desordenada para nós, não está em nenhuma ordem que nós conseguimos identificar. Essa lista de livros é pequena, então nós conseguimos ir guardando na memória, mais ou menos, a ordenação.

Vamos ver qual é o mais barato? Eu olho aqui, o de JavaScript é o primeiro da lista, 25,00 reais, é o único livro que eu tenho. Depois tem o de PHP, que é 15,00. O livro de PHP é mais barato que o de JavaScript, então guardei isso na memória.

Tem o de Java de 30,00 reais, o de Elixir de 50,00. Tenho na cabeça que o de PHP ainda é o mais barato, 15,00 reais. O de Go por 45,00 e de Python por 20,00. Então, dá para guardar na memória que os mais baratos são de PHP, de JavaScript e o de Python.

O de PHP do 15,00, o de Python por 20,00 e o de JavaScript por 25,00. Temos 50 reais, mas dá para compensar o resto com o cartão. Então, vamos pensar no que fizemos.

Na nossa cabeça, nós guardarmos alguns valores enquanto íamos percorrendo uma lista. Então, vamos dar uma olhada no que conseguimos fazer, de novo, anotando mais ou menos os passos que nós percorremos.

Vou voltar minha lista ao que ela era. Vamos percorrer. Vamos dizer que essa lista de livros é um array de livros, podemos tratar dessa forma. Como que na nossa cabeça nós criamos mais ou menos um passo a passo de como resolver essa ordenação de livros?

Começamos no que seria a primeira posição da nossa lista. Temos um valor só, não temos o que fazer com ele. Mas agora, passando para o segundo valor, eu tenho dois valores, 25,00 e 15,00, já consigo comparar.

Então, eu consigo já passar, por exemplo, para o primeiro valor da lista o meu livro de 15,00 reais, então o livro de 15,00 está guardado como o mais barato. E, em seguida, ir passando para os próximos da lista.

Então, agora eu sei que o livro de 15,00 é mais barato. Tenho em seguida um livro de 25,00, um livro de 30,00 – ok, por enquanto está ordenado –, um livro de 50,00 – por enquanto está ordenado –, depois do livro de 50,00, eu tenho o livro de 45,00.

Ok, o livro de 45,00 é mais barato que o de 50,00, então já sei que o de 50,00 não está entre os livros mais baratos, posso trocá-los de lugar. E meu último livro da lista é um livro de 20,00, que eu já sei que é mais barato que é de 45,00, que o de 50,00, que o de 30,00 e que o de 25,00.

Então, posso ficar trocando todos os meus livros de lugar até eu, na minha cabeça, fazer algo parecido com uma lista ordenada. Agora, se eu quiser, por exemplo, só o livro mais barato, é o livro de 15,00 reais; se eu quiser os três primeiros livros eu já sei que são os livros de PHP, Python e JavaScript, 15,00, 20,00 e 25,00 reais, e por aí vai.

Então, vamos um pouco além de guardar as coisas na cabeça. Como vamos trabalhar com JavaScript, nós podemos supor que a nossa lista de livros é um array, como já tínhamos conversado. Os arrays no JavaScript começam com 0, então nós temos uma lista que vai do índice 0 até o índice 5.

Como é que nós pensamos, na nossa cabeça, para guardar os valores? Nós meio que fomos guardando na nossa cabeça sempre qual era o valor mais barato.

Então, na nossa cabeça, nós percorríamos a lista. Vi primeiro o livro de 25,00, então o livro de 25,00, quando nós começamos a percorrer essa lista, é o menor. Só tenho um valor, 25,00, é o único valor que eu tenho e também é o valor menor.

Então, meu valor atual é o índice 0 e meu valor menor também é o índice 0. Passando para o próximo item da lista, o índice 1 do nosso array, agora eu tenho um livro de 15,00.

15,00 é menor do que 25,00, então o meu atual, o livro que estou verificando agora, é o livro que está no índice 1, e o meu menor também é o índice 1, porque 15,00 é menor do que 25,00.

Eu sei que agora, passando para frente, estou no índice 2. O índice 2 do meu array é um livro de Java, que é de 30,00 reais, então o meu atual agora passa a ser 2, o terceiro elemento da minha lista.

Ele não é menor do que 15,00, 30,00 não é menor do que 15,00, então o meu menor continua sendo o 15,00 reais. Eu mantenho isso na cabeça e mantenho isso na minha “variável mental” que estou chamando de menor.

Passamos para o próximo, Elixir, que está no índice 3 do array, sendo o quarto item, o quarto elemento. 50,00 ainda não é menor do que 15,00, então meu item menor continua sendo o PHP, que está no índice 1.

Passamos para a frente, agora vou para o próximo da lista, que é o livro de Go, no índice 4. Então, atualmente, estou analisando o 4. 45,00 também não é menor do que 15,00, então, na minha variável menor, continuo guardando o livro de PHP.

E, por último, eu passo para o último elemento do array, que é o índice 5, é o sexto elemento, que é um livro de Python que é 20,00 reais. 20,00 não é menor do que 15,00 também, então continuo a minha variável menor, minha variável mental, continua guardando o livro que estava no segundo elemento, o índice de número 1 do array.

Então, no final, o que nós fazemos na nossa cabeça sem perceber? Nós percorremos um array, percorremos uma lista de elementos e guardamos na cabeça, na nossa variável mental que eu chamei de menor, o índice – qual era o produto, na verdade, na cabeça nós não guardamos por índice –, qual era o produto que tinha o menor preço.

Que é o de PHP, que no array de JavaScript está no índice 1, e por aí vai. Então, o que nós fizemos foi basicamente não compilar, porque o JavaScript não é uma linguagem compilada, mas nós interpretamos, fizemos um pequeno programa que rodou sem nem percebermos – nós fazemos isso muitas vezes por dia –, e o que nós criamos na nossa cabeça foi um algoritmo.

Então, o que é um algoritmo? O que é essa sequência que nós criamos na cabeça e criamos com programas de computador? Segundo a definição da Wikipedia, podemos colocar aqui, o algoritmo é uma sequência finita de ações executáveis que visam obter uma solução para um determinado tipo de problema.

Dá para traduzirmos essa explicação, traduzir algoritmo como basicamente tudo que nós fazemos, também no dia a dia, e as instruções que damos para o computador que envolvam sequências de passos definidas.

Então, por exemplo, o que mais nós fazemos no dia a dia que podemos mudar para um algoritmo? Quando seguimos uma receita. Então, vamos ver, por exemplo, uma receita de bolo é uma sequência finita de ações executáveis, nós executamos todas as partes da receita, que visa obter uma solução para um determinado tipo de problema.

No caso, falta de bolo, um aniversário, vontade de comer bolo, por exemplo. Na vida real, o que nós fazemos? Nós dividimos um algoritmo de uma receita de bolo em vários passos, nós não percebemos.

Por exemplo, o primeiro passo seria conferir se temos todos os ingredientes. E tem condicionais nesses passos. Por exemplo, podemos dizer que, se não tiver ingredientes, o que nós fazemos? Nós saímos para comprar o que falta ou desencanamos?

Se desencanamos de fazer o bolo, o restante do programa, que é fazer o bolo em si, nem é executado. E tem uma outra coisa que fazemos também, nós acabamos dividindo o algoritmo de fazer um bolo em várias partes pequenas sem perceber.

Não é só as duas partes principais de ver sem tem todos os ingredientes, tem várias coisas que aprendemos no dia a dia de fazer bolo. Por exemplo, conferir os ingredientes é uma, para não esquecermos no final de botar o fermento que não tem fermento, e também algumas outras coisas.

Se você faz bolo com ovos, por exemplo, você vai querer quebrar o ovo em um pote ao invés de quebrar o ovo na massa, porque o ovo pode estar podre. Essa é uma instrução que, normalmente, nós aprendemos, recebemos essa instrução pronta, alguém nos fala, alguém nos dá essa dica.

Você pegar o ovo, tirar o ovo do fluxo do bolo, quebrar em um pote e voltar, é uma pequena parte que nós separamos. Então, na vida real, nós escrevemos algoritmos na cabeça, nós programamos esses algoritmos, terminamos as nossas sequências finitas de instruções – por exemplo, fazer um bolo, botar no forno etc. –, só que não percebemos que fazemos isso na cabeça.

E não só nós seguimos essas sequências de passos, como também fazemos essas pequenas reparações, o que seriam algoritmos menores, algoritmos de ver se tem todos os produtos, se tem tudo que nós queremos, se não tem, compra, ou se não tem, desencana, não cumpre o resto.

Nós podemos traduzir todo esse rolê do bolo que nós fizemos para o nosso problema de encontrar o livro mais barato em uma lista desordenada. Essa história de quebrar o ovo no pote, de aprendermos a fazer bolo com o tempo, recebendo diversas dicas, é que existem vários algoritmos já estabelecidos, já prontos para vários problemas comuns de programação.

Isso é mais ou menos o que vamos ver nesse curso: como pensamos em algoritmos, como testamos algoritmos, vamos ver alguns que já existem e se eles funcionam para nós, se eles são o melhor caso etc.

Porque um mesmo problema, por exemplo, ordenar uma lista, fazer um bolo, pode ter mais de uma forma de ser resolvido, e a escolha errada também pode causar problemas.

Por exemplo, eu tenho um algoritmo de me trocar e eu posso escolher colocar o tênis antes de colocar a calça. Funciona? Funciona, mas obviamente, colocar o tênis antes de colocar a calça vai ser muito mais trabalhoso do que colocar a calça antes de colocar o tênis.

E por aí vai. Então, vamos dar uma olhada como transformamos esse algoritmo mental nosso em JavaScript, mas isso vamos ver no próximo vídeo.

Pensando em algoritmos - Do papel para o código

Agora que já temos o nosso "algoritmo mental" do fluxo que fizemos em JavaScript, vamos escrever esse código. Então, como fazemos para passar aquele fluxo que pensamos que criamos direto na página da nossa livraria? Vamos passar isso para o JavaScript, então.

Primeira coisa que vamos precisar é criar um array, então vou criar const precosLivros. Por enquanto, criamos somente um array com o preço de cada livro, para começarmos em pequenos passos.

Os preços são [25, 15, 30, 50, 45, 20]. Então, um array em JavaScript. Nós precisamos guardar em algum lugar aquilo que eu estava chamando de variáveis mentais – agora não vai ser, agora vamos fazer no JavaScript.

Uma que guarde o valor atual que estamos vendo, qual o produto atual que estamos analisando, vou chamar de let atual. Vou iniciá-la com 0, vai ser o primeiro índice do array que estamos trabalhando.

E um outro let que vou chamar de maisBarato, que também vou iniciar com 0. É aquele onde vamos guardar - que estávamos guardando na cabeça - qual é o produto, qual é o índice do array que tem o menor valor. No caso do nosso array, teria que guardar o 15 mais do que qualquer outro.

O que temos que fazer agora? Temos que percorrer toda essa lista de livros, confirmar qual é o mais barato de todos, porque sabemos na cabeça, mas agora o JavaScript tem que nos dizer.

Podemos usar uma das várias formas que o JavaScript tem para trabalhar com loops, com laços de repetição, o que temos que fazer é percorrer listas, percorrer um array, que é um for. Então, vou criar um for que vai começar com let.

Vou chamar a variável inicial desse for de atual, então for (let atual = 0;). Já que estamos iniciando, dentro do nosso for, uma let atual, nós não precisamos iniciá-la do lado de fora, nós podemos trabalhar só com a variável atual que está dentro do for, já vai fazer o mesmo trabalho.

Vamos percorrer esse array enquanto atual for menor do que o tamanho do nosso array de livros, então (let atual = 0; atual < precosLivros.length;), com “gth” no final – sem errar, porque eu sempre erro e troco as últimas letras.

Vamos atualizar a nossa variável atual, vamos incrementá-la de um em um, atual++, para ir pulando de índice em índice do array. E aqui dentro vamos criar o nosso //código.

Se lembrarmos a forma como nós criamos esse algoritmo na nossa cabeça – vou voltar na nossa página –, o que tem que ser feito dentro desse for nós já falamos. Se o produto atual for menor, ele se torna o mais barato.

Então, se o que nós estivermos vendo no momento na lista, por exemplo, “1” e “PHP”, ele é o que nós estamos vendo na lista? Ele é o de preço menor do que tínhamos antes? É. Então, ele se torna o menor, ele se torna o mais barato. E por aí vai.

Nós meio que falamos, na cabeça, o que temos que transformar em código. Então, voltando para o nosso for, o que temos que fazer é uma condição, if.

Se o produto atual, for o mais barato da lista, nós o guardamos dentro da nossa variável “preço menor”. No caso, eu chamei de maisBarato, então ele vai ser o mais barato e nós vamos guardar o número de índice dele dentro da nossa variável let maisBarato.

A nossa condição é if (precosLivros), que é o nome do nosso array, na posição [atual], for menor do que nós tínhamos anteriormente – o que tínhamos anteriormente?

Nós começamos com “0” para comparar, então o primeiro livro que nós comparamos, ainda não tem muito o que ser comparado. Se só temos um livro de 25, ele é o atual e é também o mais barato, então estamos começando tudo com 0.

Então, vamos dizer que precosLivros na posição maisBarato. Lembrando que as variáveis guardam valores inteiros que traduzimos como índices do array. Então, precosLivros na variável atual é precosLivros na posição 0, ou seja, na posição 25.

Vou até marcar com o comentário aqui, a posição 0. E precosLivros na posição maisBarato, o maisBarato também é uma variável que está guardando 0, e 0 é 25, então é onde estamos começando.

Se a atual for menor do que já está guardado como maisBarato, vamos fazer alguma coisa, ou seja, temos que fazer com que o livro na posição atual se torne o mais barato – esquece o que tinha antes.

Então, nós começamos na posição 0, mas, se a posição 1 for mais maisBarato, esquece o 0 que estava guardado dentro da variável e vamos colocar o 1 aqui.

Então, o que tem que acontecer? maisBarato = atual. Nós declaramos uma let na nossa linha 4, ou seja, podemos substituir o valor dela de 0 para 1, de 1 para 2, de 2 para 3, de acordo com o índice onde está o menor valor do array.

No caso, o 15, que já sabemos, olhando, que é o índice 1, mas o JavaScript ainda não sabe, ele vai ter que processar isso para nós.

A última coisa a fazer, depois que sai desse for, é um console.log e olivro mais barato custa e podemos colocar, com template strings aqui, abrir cifrão e chaves, colocar ${precosLivros}, que é o nome do nosso array, em qual posição? Na posição maisBarato.

Porque, lembrando, a partir do momento que o JavaScript entra no for, ele vai percorrer o for inteiro antes de continuar. Então, o console.log que nós colocamos por último, na linha 12, só vai ser executado depois que passar por todo o array.

Então, nesse momento, nossa variável maisBarato teoricamente já está atualizada, passou pelo array inteiro, e já está guardando o que é realmente o menor valor da lista.

Então, é precosLivros na posição que não sabemos – sabemos que é 1, mas o JavaScript ainda não. maisBarato que vai ter aqui um número entre 0 e 5 guardado dentro dessa variável.

Vou salvar, venho no terminal e mando executar com node index.js, que é o nome que eu criei para esse arquivo. Então, o livro mais barato custa 15, ou seja, nós já sabíamos e o JavaScript agora também já sabe.

Porque nós fizemos com que o JavaScript percorresse, com o código, exatamente o mesmo caminho que nós fizemos mentalmente usando o nosso site, usando as nossas variáveis.

Nós fizemos o que chamamos de “teste de mesa”, vou deixar um material extra para vocês sobre o que é um teste de mesa, mas, basicamente, nós fizemos uma interpretação do código na nossa cabeça e fomos marcando em cada momento do loop, em cada momento do processamento, o que tinha guardado em determinadas variáveis.

Aqui eu chamei a variável de “menor”, no código eu acabei chamando de maisBarato, mas é a mesma variável. E a variável “atual”, que é a que está fazendo o controle desse array, de passar índice por índice.

Então, o que nós fizemos foi criar o nosso primeiro algoritmo para resolver o nosso primeiro problema que é encontrar o livro mais barato em uma lista desordenada.

Fizemos isso a partir da nossa cabeça e sem perceber, é uma coisa que fazemos todos os dias. Com o código, podemos passar os mesmos passos que fazemos na cabeça para o código, só fazendo de uma forma que o JavaScript entende.

Mas, como falei antes, existe mais de uma forma de resolver um problema. Sempre ou quase sempre existe. Vamos dar uma olhada, continuaremos a estudar os nossos algoritmos.

Sobre o curso JavaScript I: algoritmos de ordenação

O curso JavaScript I: algoritmos de ordenação possui 141 minutos de vídeos, em um total de 43 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:

• Pensando em algoritmos
• Carregamento de arquivos
• Capturando links
• Usando a linha de comando
• Validando links