Escrevendo um algoritmo

Nós já sabemos o que é um algoritmo. Ele é um texto com diversas instruções. Normalmente, podemos imaginar que um algoritmo será executado por um certo robozinho. Esse robô é o processador que irá executar as instruções do algoritmo, então é fundamental que só demos a ele ordens bem básicas, que ele seja capaz de cumprir.

Assim, queremos escrever um algoritmo que só contenha instruções elementares. Mais do que isso, também é importante projetar um mecanismo que diga ao robô qual instrução ele deverá executar em seguida e quando o algoritmo termina. Por isso, nosso algoritmo terá algumas instruções de controle que digam a ordem e a forma em que as ações são executadas.

Estruturas de controle

Vamos listar as estruturas de controle mais comumente utilizadas ao escrever um algoritmo:

O sequenciamento direto é a convenção do nosso algoritmo que determina que uma instrução escrita antes no texto deve ser executada antes. Normalmente é determinada implicitamente. Por exemplo, se escrevermos uma instrução por linha, então sabemos que cada linha é executada em ordem; se separarmos instruções por ponto-e-vírgula, então podemos imaginar que esse ponto-e-vírgula significa "e depois faça", etc.
O desvio condicional é uma estrutura de controle que permite que a execução de um algoritmo tome caminhos diferentes, dependendo da entrada e dos dados já computados. Normalmente tem a forma "se Q, então faça A, do contrário faça B", ou apenas "se Q, então faça A". Nessas frases, Q é uma condição, ou uma pergunta, cuja a resposta é sim ou não e pode ser testada por nosso robô.

Você pode se perguntar como a execução de um algoritmo pode levar tempo diferente se o tamanho do texto que o descreve é fixo. Se tivéssemos apenas os tipos de controle acima, então toda execução levaria o mesmo tempo. Para executarmos uma instrução ou um conjunto de instruções por um número variável de vezes, precisamos das chamadas estruturas iterativas. Cada parte da execução em que executamos esse conjunto de instruções uma vez é chamada de iteração.

A iteração limitada é a estrutura mais comum de iteração e é normalmente da forma "repita A exatamente N vezes" ou muitas outras vezes pode ser da forma "para cada item I da lista L, faça A". Isso foi útil, por exemplo, no exemplo da soma dos preços da lista de compra, que vimos anteriormente.
A iteração condicional é outra estrutura de controle iterativa que é utilizada quando não sabemos no início quantas vezes precisamos iterar. Normalmente, tem as formas "repita A até que Q valha" ou "enquanto Q, faça A". De novo, Q é uma condição que pode ser testada por nosso robô.

As estruturas iterativas normalmente são chamadas de laços ou loops.

Vamos reescrever o algoritmo para exemplo da lista de compras. Nós vamos supor que nosso algoritmo recebe, não somente a lista de compras, como o número de itens que ela contém, que representaremos pela letra N.

(1) tome nota do número zero; aponte para o primeiro item da lista;
(2) faça o seguinte N - 1 vezes:
    (2.1) adicione o valor do item atual ao número anotado;
    (2.2) aponte para o próximo item da lista;
(3) adicione o valor do item atual ao número anotado;
(4) devolva como saída o número anotado.

Combinando estruturas

O que torna os algoritmos particularmente ricos é a possibilidade de combinar as diversas estruturas de controle. Por exemplo, podemos executar um laço dentro do conjunto de ações de uma estrutura condicional. Mais do que isso, podemos executar um laço dentro do conjunto de ações de outro laço. Nesse último exemplo, chamamos o primeiro de laço interno e o segundo de laço externo. E assim por diante!

Já deve dar para perceber que os algoritmos podem ficar cada vez mais diversos e mas ricos — e, algumas vezes, mais complexos! Cada algoritmo pode ser mais ou menos complicado. Isso vai depender do problema que queremos resolver.

Vamos tentar fazer um algoritmo que ordena um conjunto de cartas!

Uma maneira de fazer isso é primeiro colocar as cartas uma do lado da outra. Depois, basta percorrer as cartas várias vezes, da esquerda para a direita trocando cartas adjacentes que estejam fora de ordem. Quando não encontrarmos nenhum par de cartas fora de ordem, sabemos que as cartas estão ordenadas. Esse é um algoritmo chamado de bubble sort, ou ordenação da bolha. A ideia é que as cartas maiores vão sendo empurradas para o final, como se fossem bolhas.

Na verdade, o bubblesort é um algoritmo bem lento e você ainda vai aprender diversos algoritmos que são muitas vezes mais rápidos. Mas, por enquanto, vamos nos concentrar em escrever esse algoritmo. Primeiro, precisamos saber quantas vezes precisamos percorrer a sequência de cartas. Na primeira vez que percorremos as cartas, deve ser fácil convencer-se de que a maior carta estará no final. Na segunda vez, a segunda maior carta já estará na posição correta, e assim por diante. Assim, se o número de cartas é N, então basta percorrer o baralho N - 1 vezes.

(1) repita o seguinte N − 1 vezes:
    (1.1) aponte para a primeira carta;
    (1.2) repita o seguinte N - 1 vezes:
        (1.2.1) compare a carta apontada atualmente com a seguinte;
        (1.2.2) se as cartas comparadas estão fora de ordem, inverta-as;
        (1.2.3) aponte para a próxima carta.

Esse é um exemplo de algoritmo em que utilizamos e combinamos diversas estruturas de controle. Tente identificá-las!

Desenhando um algoritmo

Ao invés de escrever um algoritmo, também podemos representá-los utilizando desenhos. Há diversas maneiras de desenhá-los, mas talvez a maneira mais comum é criar o que chamamos de "diagrama de fluxo", ou em inglês, "flowchart".

Em um diagrama de fluxo, cada instrução elementar é representada por um retângulo e cada desvio condicional é representado por um losango. O objetivo é entender qual o fluxo de execução do algoritmo. Assim, saindo de cada retângulo há um arco que aponta para a próxima instrução a ser executada. Como a instrução executada depois de um desvio condicional depende da resposta, sim ou não, a partir de um losango há dois arcos, um para cada possibilidade.

Vamos tentar fazer um desenho do nosso algoritmo.

Perceba que as estruturas iterativas correspondem ao desenho de um ciclo no diagrama de fluxo. Isso explica a nomenclatura de laço.

Sub-rotinas

Algumas vezes, os algoritmos podem ficar mais e mais complicados. Assim nossos algoritmo ou diagramas de fluxo podem ficar cada vez maiores. Vamos ver um exemplo de como isso pode acontecer.

Suponha que, na nossa lista de compras, há, não somente o valor de cada item, mas também o tipo. Assim, cada item pode ser alimentação, limpeza, vestuário, eletrônico etc. Dependendo do supermercado a que vamos, não vamos conseguir comprar todos os itens. Se no supermercado mais próximo pudermos comprar apenas itens de alimentação e limpeza, então precisamos saber o quanto vamos gastar com esses tipos de item. Vamos modificar o algoritmo anterior.

(1) tome nota do número zero
(2) aponte para o primeiro item da lista;
(3) faça o seguinte N - 1 vezes:
    (3.1) se o item atual é do tipo "alimentação"
        (3.1.1) adicione o valor do item atual ao número anotado;
    (3.2) aponte para o próximo item da lista;
(4) se o item atual é do tipo "alimentação"
    (4.1) adicione o valor do item atual ao número anotado;
(5) aponte para o primeiro item da lista;
(6) faça o seguinte N - 1 vezes:
    (6.1) se o item atual é do tipo "limpeza"
        (6.1.1) adicione o valor do item atual ao número anotado;
    (6.2) aponte para o próximo item da lista;
(7) se o item atual é do tipo "limpeza"
    (7.1) adicione o valor do item atual ao número anotado;
(8) devolva como saída o número anotado.

É claro que há algoritmos mais simples para essa tarefa, mas esse podemos fazer diversas observações do algoritmo que escrevemos acima. Primeiro, o texto do algoritmo ficou muito maior. Mais importante do que isso, é muito mais difícil entender o que está fazendo esse algoritmo. Tente desenhar o diagrama de fluxo correspondente.

Além disso, observamos que há dois trechos do algoritmo que são muito parecidos e tudo que muda é o tipo de alimento. Podemos então tentar escrever esse trecho de código apenas uma vez utilizando um parâmetro ao invés do tipo de alimento. Esse trecho de código é chamado de sub-rotina ou procedimento.

SOMAR ITENS DA CATEGORIA (X)
(1) aponte para o primeiro item da lista;
(2) faça o seguinte N - 1 vezes:
    (2.1) se o item atual é do tipo X
        (2.1.1) adicione o valor do item atual ao número anotado;
    (2.2) aponte para o próximo item da lista;
(3) se o item atual é do tipo "X"
    (3.1) adicione o valor do item atual ao número anotado;

No texto acima, X é um parâmetro que será substituído pelo tipo de alimento quando invocarmos essa sub-rotina. Com esse texto, agora podemos invocar ou chamar a nossa sub-rotina duas vezes no algoritmo principal.

(1) tome nota do número zero
(2) SOMAR ITENS DA CATEGORIA ("alimentação")
(3) SOMAR ITENS DA CATEGORIA ("limpeza")
(4) devolva como saída o número anotado.

Compare esse novo algoritmo com o algoritmo anterior. Ele não ficou muito mais simples? É importante observar que agora utilizamos uma instrução que antes não era permitida, que é SOMAR ITENS DA CATEGORIA. Esta não é uma instrução elementar do nosso processador original, mas utilizamos como se fosse. O que estamos fazendo é análogo a ensinar o nosso robozinho a realizar uma nova atividade, de forma que não precisamos explicar de novo como fazê-la. Dizemos que estamos criando uma nova abstração, escondendo os detalhes de implementação.

Podemos desenhar agora um diagrama de fluxo substituindo o trecho do algoritmo da sub-rotina por um retângulo, como uma instrução elementar. Faça isso.

Tipos e estrutura de de dados

Por enquanto falamos apenas de números anotados, de listas de itens de compra, de apontamentos para itens, de ingredientes. Alguns desses elementos aparecem na entrada e na saída, enquanto outros aparecem como objetos intermediários computados durante a execução do algoritmo. A todos esses objetos, chamaremos de dados.

Tipos

Os vários dados aparecem nos mais diversos sabores, ou mais precisamente, nos mais diversos tipos. Os tipos mais comuns utilizados nos computadores são os números, que podem ter diversos subtipos, e strings, que representam palavras ou textos nos mais diversos alfabetos.

Nos computadores que consideraremos, os dados são sempre representados de alguma maneira em particular na memória do computador. Assim, precisamos adotar convenções para representar os objetos tratados pelos algoritmos como uma sequência bem definida de dados. Por exemplo, enquanto tratamos números inteiros no formato decimal, a representação desses números na memória é binária. Se quisermos representar objetos mais complicados, como uma imagem, vamos precisar definir representações apropriadas — algumas vezes um tanto quanto complicadas, outras vezes mais simples.

É importante que entendamos exatamente qual é o tipo de cada dado que tratamos no algoritmo, pois cada tipo permite operações distintas. Por exemplo, podemos dividir dois números, mas não podemos dividir duas strings!

Variáveis

No algoritmo da soma, referimo-nos a um dado simplesmente como "valor anotado", que é inicializado com 0 e depois acumula o valor dos itens de compra. O que estamos fazendo é utilizar uma variável. Uma variável não é o valor de um dado em si; ao invés disso, podemos entender uma variável como uma pequena caixa ou célula onde um determinado valor pode ser armazenado. Cada variável tem um tipo correspondente; assim, podemos imaginar que nessa caixa só cabem valores do tipo correspondente.

Normalmente, damos um nome a essa caixa. Poderíamos, por exemplo, ao invés de dizer "número anotado", chamar essa variável de "subtotal".

Em Computação, chamamos de variável uma célula que pode conter diversos valores distintos em diferentes momentos, ao contrário da Matemática, em que uma variável é apenas um símbolo que representa um valor desconhecido.

Como o valor de uma variável pode mudar, necessitamos de instruções específicas para alterar o valor de uma variável. Essa instrução é chamada de atribuição. Normalmente escrevemos algo como "Atribua valor V à variável X", ou utilizamos uma notação mais simples, como X $\gets$ V, que devemos ler como "a variável X recebe o valor de V".

Também podemos atribuir um valor de uma expressão, como em X $\gets$ V+1, em que queremos atribuir à variável X o valor de V mais uma unidade. Devemos tomar um cuidado especial, já que muitas vezes o novo valor depende do valor anterior da variável. Assim, podemos ter a instrução X $\gets$ X+1 que significa que o valor da variável X deve ser mudado e que o novo valor é o valor anterior mais um.

Coleções de dados

Retomemos o exemplo da nossa lista de compras. Para representar a entrada, falamos de uma "lista de compras". Assim, cada item a ser comprado é uma parte da lista. Podemos querer armazenar cada item em um conjunto de variáveis. Por exemplo, o primeiro item na variável X, o segundo na variável Y e o terceiro na variável Z. Mas logo você deve perceber que essa estratégia não é boa se tivermos um lista de compras com mais ou menos do que três itens. Para listas maiores, precisaríamos definir mais variáveis e, para listas menores, teríamos variáveis que não fazem sentido!

Como nosso objetivo é escrever um texto de tamanho fixo, mas que possa ser executado com listas de qualquer tamanho, precisamos de uma maneira de nos referir a esses elementos de maneira uniforme. Para isso, vamos utilizar o que chamamos de lista. Dependendo do contexto, também serão chamadas de vetores ou arranjos unidimensionais.

Para tomar um exemplo, vamos tentar representar a nossa sequência de cartas usando uma lista. Por simplicidade, todas as cartas tem valores diferentes, então vamos ignorar os naipes e supor que o ás é representado pelo número 1. Assim, a sequência anterior poderia ser representada pela seguinte lista.

Na figura acima, a variável cartas representa toda a sequência de cartas, mas ainda precisamos de algum mecanismo para nos referir a cada um dos elementos. Poderíamos dizer simplesmente "o primeiro elemento de cartas", mas há um jeito melhor. Vamos adotar uma notação de colchetes, assim a primeira carta será cartas[1], a segunda será cartas[2] e assim por diante.

Com isso, podemos tentar reescrever nosso algoritmo bubblesort.

(1) repita o seguinte N − 1 vezes:
    (1.1) X <-- 1;
    (1.2) enquanto X < N
        (1.2.1) se cartas[X + 1] < cartas[X], então inverta esses elementos;
        (1.2.3) X <-- X + 1.