Algoritmos e Lógica de Programação

O que mais cai

Do que trata o tópico

Este tópico ensina a base de toda a programação: o que é um algoritmo, como ele se escreve com as estruturas de controle, como as variáveis e os subprogramas guardam e trocam dados, quais pseudolinguagens e linguagens servem ao ensino e quais algoritmos clássicos (recursão, busca e ordenação) aparecem nas provas.

Conteúdo

Definição de Algoritmos e Estruturas de Controle

Um servidor precisa calcular a média de 300 candidatos e dizer quem foi aprovado. Se cada colega fizer a conta do seu jeito, o resultado muda de pessoa para pessoa. A solução é uma sequência de passos que qualquer pessoa, ou computador, execute sempre da mesma forma.

Essa sequência de passos é o algoritmo: um conjunto finito de instruções bem definidas, em ordem, que resolve um problema em um tempo finito. A receita de bolo é o exemplo do dia a dia, mas o computador não interpreta frases vagas como "asse até ficar bom".

Características do algoritmo. Donald Knuth descreve cinco características que a banca cobra com frequência:

1. Finitude: o algoritmo termina após um número finito de passos.
2. Definição: cada passo é preciso e sem ambiguidade, isto é, só admite uma interpretação.
3. Entrada: o algoritmo tem zero ou mais entradas, os dados que recebe antes ou durante a execução.
4. Saída: o algoritmo tem uma ou mais saídas, os resultados que entrega.
5. Efetividade: cada passo é simples o bastante para ser executado de fato, em tempo finito.

A entrada pode ser zero (um algoritmo que imprime os números de 1 a 10 não recebe nada), mas a saída não, porque um algoritmo sem resultado não resolve problema algum. Um laço que nunca termina pode estar num programa, mas não é algoritmo, porque viola a finitude.

Formas de representação. A descrição narrativa usa a língua natural ("leia as duas notas, some e divida por dois") e permite ambiguidade. O fluxograma usa símbolos ligados por setas, e o pseudocódigo usa uma linguagem estruturada em português. A parte de pseudolinguagens detalha os dois.

A programação estruturada. Corrado Böhm e Giuseppe Jacopini mostraram que qualquer algoritmo pode ser escrito com só três estruturas de controle: a sequência, a seleção (decisão) e a repetição (laço). Edsger Dijkstra criticou o desvio incondicional (o goto), que salta para qualquer ponto do código. A programação estruturada usa só as três estruturas, cada uma com uma entrada e uma saída.

Sequência. Na sequência, os comandos executam um depois do outro, na ordem escrita.

Seleção. A seleção escolhe qual bloco executar a partir de uma condição lógica, isto é, uma expressão que vale verdadeiro ou falso. Há quatro formas:

1. Seleção simples (se ... entao ... fimse): se a condição é verdadeira, o bloco executa; se é falsa, nada acontece.
2. Seleção composta (se ... entao ... senao ... fimse): um bloco para o verdadeiro e outro para o falso. Sempre um dos dois executa.
3. Seleção encadeada: um se dentro do senao de outro, para testar várias faixas (nota abaixo de 5, de 5 a 7, acima de 7).
4. Seleção múltipla (escolha ... caso, o switch de C e Java): compara uma variável com vários valores fixos e executa o caso que bate.

No switch de C e Java, sem o break no fim do case, a execução continua nos casos de baixo, mesmo que o valor não bata com eles. Esse efeito se chama queda (fall-through).

Repetição. A repetição executa o mesmo bloco várias vezes: o cálculo da média dos 300 candidatos é escrito uma vez, dentro de um laço. Há três tipos de laço, que diferem pelo momento do teste da condição:

1. Enquanto (enquanto ... faca, o while): testa a condição antes de cada volta. Se a condição é falsa logo na primeira vez, o bloco não executa nenhuma vez.
2. Repita ... até (repita ... ate): testa a condição depois de cada volta. O bloco executa pelo menos uma vez, e o laço para quando a condição fica verdadeira.
3. Para (para i de 1 ate 10 faca, o for): usa uma variável de controle que começa num valor, avança a cada volta e para no valor final. Serve quando o número de voltas é conhecido antes de o laço começar.

Em C e Java, o laço com teste no fim é o do ... while, que continua enquanto a condição é verdadeira. O repita ... ate do Portugol faz o contrário: continua enquanto a condição é falsa e para quando ela fica verdadeira. As duas estruturas executam o bloco pelo menos uma vez.

O contador soma sempre o mesmo valor (cont <- cont + 1) e conta ocorrências. O acumulador soma um valor que muda (soma <- soma + nota) e guarda um total. Os dois recebem um valor inicial antes do laço, em geral zero.

Se o bloco não altera nenhuma variável da condição, o laço nunca termina: é o laço infinito. Para parar a leitura de dados sem saber quantos virão, o algoritmo usa um valor sentinela, um valor especial (como -1 numa lista de idades) que avisa o fim.

Operadores. As condições usam três grupos de operadores. Os aritméticos fazem conta: além de soma, subtração, multiplicação e divisão, há div (quociente da divisão inteira) e mod (resto da divisão inteira). Os relacionais comparam (=, <>, <, >, <=, >=), e os lógicos juntam condições: e (verdadeiro só se as duas partes são verdadeiras), ou (verdadeiro se ao menos uma é verdadeira) e nao (inverte o valor).

A ordem de avaliação, sem parênteses, é: primeiro os aritméticos, depois os relacionais e por último os lógicos. Entre os lógicos, o nao vem antes do e, e o e vem antes do ou. Assim, nao V e F ou V vale verdadeiro: nao V dá falso, falso e F dá falso e falso ou V dá verdadeiro.

Exemplo resolvido: o algoritmo abaixo soma os números pares de 1 a 6. A técnica para descobrir o que ele mostra é o teste de mesa, isto é, executar o algoritmo à mão e anotar o valor de cada variável a cada passo.

soma <- 0
i <- 1
enquanto i <= 6 faca
   se i mod 2 = 0 entao
      soma <- soma + i
   fimse
   i <- i + 1
fimenquanto
escreva(soma)

1. Antes do laço: soma vale 0 e i vale 1.
2. Com i = 1, o resto de 1 por 2 é 1, a condição do se é falsa e soma continua 0. O i passa a 2.
3. Com i = 2, o resto é 0 e soma passa a 0 + 2 = 2. O i passa a 3.
4. Com i = 3, nada muda na soma. Com i = 4, soma passa a 2 + 4 = 6.
5. Com i = 5, nada muda. Com i = 6, soma passa a 6 + 6 = 12.
6. O i passa a 7, a condição 7 <= 6 é falsa e o laço termina.
7. Resultado: o algoritmo mostra 12.

Na prática, um setor de protocolo conta os processos atrasados de uma lista com um laço para que percorre a lista, um se que testa o prazo e um contador zerado antes do laço. A diferença que a banca mais troca é entre o enquanto, que pode não executar nenhuma vez, e o repita, que executa ao menos uma vez.

O erro comum é esquecer de atualizar a variável da condição dentro do laço (laço infinito) ou de iniciar o acumulador com zero.

x = 10
cont = 0
while x > 1:
    if x % 2 == 0:
        x = x // 2
    else:
        x = 3 * x + 1
    cont = cont + 1
print(x, cont)

int op = 2;
int r = 0;
switch (op) {
    case 1: r = r + 1;
    case 2: r = r + 10;
    case 3: r = r + 100;
        break;
    default: r = r + 1000;
}
System.out.println(r);

Como a banca cobra: a banca dá um trecho de código ou de pseudocódigo com laço e seleção e pede o valor impresso, ou troca o momento do teste entre o enquanto e o repita, ou esconde a falta de break num switch.

Variáveis, Subprogramas e Passagem de Parâmetro

Um algoritmo de folha de pagamento precisa guardar o salário, os descontos e o líquido de cada servidor. A variável é o lugar para isso: um espaço da memória com um nome, que guarda um valor e permite trocá-lo durante a execução.

Toda variável tem quatro elementos: o nome (identificador), o tipo (que valores ela aceita), o valor atual e o endereço na memória. A constante é parecida, mas o valor é fixado uma vez e não muda durante a execução, como o valor de pi.

Tipos de dados. Os tipos primitivos do pseudocódigo são quatro: inteiro (números sem parte decimal, como 25), real (números com parte decimal, como 7,5), caractere (texto, como "Ana") e lógico (verdadeiro ou falso). Os compostos juntam vários valores: o vetor (mesmo tipo, acesso por índice), a matriz (vetor de duas ou mais dimensões) e o registro (campos de tipos diferentes, como nome e salário).

Identificadores. O nome da variável segue regras comuns à maioria das linguagens: começa com letra ou sublinhado, não tem espaço nem caractere especial e não pode ser uma palavra reservada, isto é, uma palavra que a linguagem usa como comando (se, enquanto, inicio). Assim, salario_base e _total são nomes válidos, mas 2nota, nota final e enquanto não são.

Declaração e atribuição. Antes do uso, a variável é declarada: o algoritmo informa o nome e o tipo, e a linguagem reserva o espaço. A atribuição grava um valor na variável e, no pseudocódigo, usa a seta (soma <- 0). A seta não é igualdade matemática: x <- x + 1 lê o valor atual de x, soma 1 e grava o resultado de volta em x.

Escopo e tempo de vida. O escopo é a região do programa em que a variável pode ser usada. A variável global é declarada fora de qualquer subprograma e vale em todo o programa. A variável local é declarada dentro de um subprograma, só vale dentro dele e some quando o subprograma termina.

Quando uma variável local tem o mesmo nome de uma global, dentro do subprograma vale a local, e a global fica escondida: é o sombreamento. Alterar a local não muda a global.

Subprogramas. Um sistema de folha calcula o desconto de previdência em vários pontos, e copiar o cálculo em cada ponto gera erro quando a regra muda. O subprograma (sub-rotina ou módulo) é um bloco com nome, escrito uma vez e chamado quantas vezes for preciso. Ele traz reaproveitamento, leitura mais fácil, teste em separado e manutenção num lugar só. Há dois tipos:

1. Procedimento: executa uma tarefa e não devolve valor para quem o chamou (por exemplo, imprimir um relatório). A chamada aparece sozinha, como um comando.
2. Função: executa uma tarefa e devolve um valor (por exemplo, calcular a média). A chamada aparece dentro de uma expressão, como m <- media(n1, n2).

Em C e Java, o procedimento é a função de retorno void, que não devolve nada. Em Pascal e no Portugol, os nomes são procedure e function, ou procedimento e funcao.

Parâmetros formais e reais. Os parâmetros formais são os nomes declarados no cabeçalho do subprograma (funcao media(a, b: real)). Os parâmetros reais, também chamados de argumentos, são os valores ou variáveis passados na chamada (media(n1, n2)). Na chamada, cada argumento se liga ao parâmetro formal da mesma posição.

Como funciona a chamada. A cada chamada, o sistema monta na pilha de execução um registro de ativação com os parâmetros, as variáveis locais e o ponto de retorno. Ao terminar, o subprograma devolve o valor (se for função), o registro sai da pilha e a execução volta ao comando seguinte ao da chamada.

Passagem de parâmetro. A forma como o argumento chega ao parâmetro formal decide se a alteração feita dentro do subprograma aparece fora dele:

1. Por valor: o parâmetro formal recebe uma cópia do valor do argumento. Alterar o parâmetro dentro do subprograma não muda a variável de quem chamou. O argumento pode ser uma constante ou uma expressão (dobra(3 + 2)).
2. Por referência: o parâmetro formal recebe o endereço da variável. Alterar o parâmetro altera a própria variável de quem chamou. O argumento precisa ser uma variável, porque uma constante ou expressão não tem endereço para ser alterado.
3. Por valor-resultado (cópia e restauração): o parâmetro recebe uma cópia na entrada, e o valor final é copiado de volta para a variável quando o subprograma termina.

No Portugol e no Pascal, a palavra var antes do parâmetro formal marca a passagem por referência. Em C, toda passagem é por valor, e a passagem por referência é simulada com ponteiros: a função recebe o endereço (&x) e altera o conteúdo pelo ponteiro (*p). O C++ tem a referência de fato, marcada com & no parâmetro.

Em Java, toda passagem é por valor. Quando o argumento é um objeto, o método recebe uma cópia da referência, e por isso pode alterar os atributos do objeto original, mas não consegue fazer a variável de quem chamou apontar para outro objeto. Em Python, o parâmetro recebe o mesmo objeto do argumento: uma lista alterada por append muda também fora, mas uma nova atribuição ao parâmetro só troca o nome local.

Exemplo resolvido: o procedimento abaixo recebe x por valor e y por referência (marcado com var).

procedimento dobra(x: inteiro; var y: inteiro)
inicio
   x <- x * 2
   y <- y * 2
fimprocedimento

a <- 3
b <- 5
dobra(a, b)
escreva(a, " ", b)

1. Antes da chamada, a vale 3 e b vale 5.
2. Na chamada, x recebe uma cópia de a (3), e y passa a apontar para a própria variável b.
3. O comando x <- x * 2 faz x valer 6, mas a cópia some ao fim do procedimento e a continua 3.
4. O comando y <- y * 2 grava 10 na variável b, porque y é o endereço de b.
5. Resultado: o algoritmo mostra 3 e 10.

Na prática, a função calculaDesconto(salario) recebe o salário por valor e devolve o desconto sem risco de alterar o salário guardado. Já o procedimento reajusta(var salario, percentual) recebe o salário por referência, porque a tarefa dele é alterar o valor guardado.

A diferença que a banca mais troca é entre parâmetro formal (no cabeçalho) e parâmetro real (na chamada). O erro comum é achar que Java passa objetos por referência: Java passa a referência por valor.

def altera(lista, n):
    lista.append(n)
    n = n + 1
    lista = [0]
    return n

v = [1, 2]
k = 5
r = altera(v, k)
print(v, k, r)

total = 100

def f(total):
    total = total + 1
    return total

def g():
    global total
    total = total + 10

g()
print(f(total), total)

Como a banca cobra: a banca mostra um subprograma com um parâmetro por valor e outro por referência e pede os valores depois da chamada, ou afirma que Java passa objetos por referência, ou troca parâmetro formal com parâmetro real.

Linguagens Educacionais e Pseudolinguagens

Quem começa a programar enfrenta dois problemas ao mesmo tempo: pensar a lógica e decorar a sintaxe de uma linguagem em inglês. As pseudolinguagens e as linguagens educacionais separam os dois problemas: o aluno pensa a lógica primeiro, em português ou com blocos visuais, e só depois aprende a sintaxe.

Pseudocódigo e Portugol. O pseudocódigo é uma forma de escrever o algoritmo com palavras da língua natural, numa estrutura parecida com a de uma linguagem de programação. Ele não tem um padrão único: cada livro e cada professor usam a sua variação. O Portugol, também chamado de português estruturado, é a pseudolinguagem com palavras em português mais usada no Brasil.

O pseudocódigo em si não é executado, porque não segue uma gramática fixa, mas algumas ferramentas executam um dialeto fixo de Portugol. As mais citadas são o VisuAlg, que interpreta o Portugol e mostra o valor das variáveis durante a execução, e o Portugol Studio, um ambiente de ensino do Portugol.

A estrutura do VisuAlg. Um algoritmo no VisuAlg tem três partes, nesta ordem:

1. O cabeçalho, com algoritmo "nome".
2. A área de declaração, aberta por var, com cada variável e o seu tipo (inteiro, real, caractere, logico).
3. O corpo, entre inicio e fimalgoritmo, com os comandos.

Os comandos principais são leia (entrada), escreva e escreval (saída, o segundo pula de linha), <- (atribuição), se, escolha, enquanto, repita e para, cada um fechado pelo seu fim (fimse, fimenquanto). A igualdade usa = e a diferença usa <>. No VisuAlg, a divisão inteira usa a barra invertida (\) e o resto usa mod ou %. No Portugol dos livros e no Pascal, a divisão inteira usa div.

Exemplo resolvido: o algoritmo abaixo lê duas notas, calcula a média e mostra se o aluno foi aprovado com média 7 ou mais.

algoritmo "media"
var
   n1, n2, media: real
inicio
   leia(n1, n2)
   media <- (n1 + n2) / 2
   se media >= 7 entao
      escreval("Aprovado")
   senao
      escreval("Reprovado")
   fimse
fimalgoritmo

1. O usuário digita 6 e 9, que vão para n1 e n2.
2. A média é (6 + 9) / 2 = 15 / 2 = 7,5.
3. A condição 7,5 >= 7 é verdadeira, e o bloco do entao executa.
4. Resultado: o algoritmo mostra "Aprovado".

O fluxograma. O fluxograma desenha o algoritmo com símbolos ligados por setas que mostram a ordem de execução. Os símbolos mais cobrados são: o terminal (retângulo de cantos arredondados ou elipse), que marca o início e o fim; o processamento (retângulo), que representa um cálculo ou uma atribuição; a decisão (losango), que tem uma saída para o sim e outra para o não; a entrada e saída de dados (paralelogramo); e o conector (círculo), que liga partes do desenho. O algoritmo da média, em fluxograma, segue os passos abaixo.

O diagrama de Nassi-Shneiderman (ou de Chapin) desenha o algoritmo em retângulos encaixados, sem setas, e só admite as estruturas da programação estruturada.

Linguagens educacionais. Algumas linguagens de programação reais nasceram para o ensino:

1. Pascal: criada por Niklaus Wirth para ensinar programação estruturada, com tipagem forte e estática e blocos begin ... end. É a origem do estilo do Portugol, inclusive do var para passagem por referência.
2. BASIC: criada por John Kemeny e Thomas Kurtz para que estudantes de áreas fora da computação programassem com facilidade.
3. Logo: ligada a Seymour Papert, conhecida pela tartaruga, um cursor que anda e risca a tela com comandos como avançar e girar. Ensina geometria e lógica para crianças.
4. Scratch: linguagem visual por blocos, criada no MIT, em que o aluno encaixa blocos coloridos em vez de digitar comandos, o que elimina o erro de sintaxe.

Na prática, uma escola de governo que oferece um curso de lógica a servidores começa com o Portugol no VisuAlg, porque o aluno escreve em português e vê o valor das variáveis a cada passo. Depois, a mesma lógica é reescrita numa linguagem real, e o aluno aprende só a sintaxe nova.

A diferença que a banca troca é entre pseudocódigo, que descreve a lógica sem padrão único, e linguagem de programação, que tem gramática fixa. O VisuAlg fica no meio: interpreta um dialeto fixo de Portugol.

O erro comum é usar = para atribuir no Portugol. No VisuAlg, o = compara, e a atribuição usa <-.

Como a banca cobra: a banca pede o símbolo de fluxograma de cada ação (losango para decisão, paralelogramo para entrada e saída), mostra um trecho de Portugol para leitura ou atribui a uma linguagem educacional a característica de outra.

Algoritmos Diversos

Um órgão tem um cadastro com 100 mil processos e precisa achar um processo em segundos, e procurar um por um demora. Os algoritmos clássicos de busca, de ordenação e de recursão resolvem esse tipo de problema com menos passos.

Complexidade e notação O. Para comparar dois algoritmos, conta-se o número de passos em função do tamanho da entrada, chamado de n. A notação O (O grande) mostra como esse número cresce quando n fica muito grande, no pior caso, ignorando constantes. Do mais rápido para o mais lento, as classes mais cobradas são:

1. O(1), constante: o tempo não depende de n (acessar o elemento de um vetor pelo índice).
2. O(log n), logarítmica: a cada passo, o problema cai pela metade (busca binária).
3. O(n), linear: um passo por elemento (busca sequencial).
4. O(n log n): ordenação eficiente (merge sort e heapsort).
5. O(n²), quadrática: dois laços encaixados sobre os dados (bolha, seleção e inserção no pior caso).
6. O(2ⁿ), exponencial: o número de passos dobra a cada elemento novo (Fibonacci recursivo simples).

O algoritmo é analisado no melhor caso, no caso médio e no pior caso, e a notação O descreve em geral o pior caso.

Recursão. A função recursiva é a que chama a si mesma para resolver uma versão menor do mesmo problema. Ela tem duas partes obrigatórias: o caso base, que resolve o problema sem nova chamada e encerra a recursão, e o passo recursivo, que chama a função com uma entrada menor, mais perto do caso base. Sem caso base, a função chama a si mesma até lotar a pilha de execução, o erro chamado de estouro de pilha (stack overflow).

O fatorial é o exemplo clássico: o fatorial de n é n vezes o fatorial de n - 1, e o fatorial de 0 é 1 (caso base). Cada chamada fica parada na pilha esperando o resultado da chamada seguinte:

1. fatorial(4) espera 4 × fatorial(3).
2. fatorial(3) espera 3 × fatorial(2).
3. fatorial(2) espera 2 × fatorial(1).
4. fatorial(1) espera 1 × fatorial(0).
5. fatorial(0) chega ao caso base e devolve 1.
6. Na volta, as contas se resolvem: 1 × 1 = 1, 2 × 1 = 2, 3 × 2 = 6 e 4 × 6 = 24.

Toda função recursiva pode ser reescrita com laço (forma iterativa). A recursão encurta o código de problemas que se dividem em partes iguais, mas gasta memória com a pilha. O Fibonacci recursivo simples recalcula os mesmos valores e tem custo exponencial; a versão com laço é linear.

Busca sequencial e busca binária. A busca sequencial (ou linear) compara o valor procurado com cada elemento do vetor, do primeiro ao último. Funciona em qualquer ordem e, no pior caso, faz n comparações: O(n).

A busca binária exige o vetor ordenado. Ela funciona assim:

1. Marca o início e o fim da faixa de busca (todo o vetor).
2. Compara o valor procurado com o elemento do meio da faixa.
3. Se é igual, achou e termina.
4. Se o valor procurado é menor, a nova faixa é a metade da esquerda; se é maior, a metade da direita.
5. Repete os passos 2 a 4 até achar ou até a faixa ficar vazia.

Como a faixa cai pela metade a cada comparação, a busca binária é O(log n). No pior caso, faz a parte inteira do logaritmo de n na base 2, mais 1, comparações: com 1.000 elementos, no máximo 10.

Exemplo resolvido: procurar o valor 23 no vetor ordenado [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], com as posições numeradas de 0 a 9 e o meio calculado como a divisão inteira de (início + fim) por 2.

1. Faixa de 0 a 9: meio = (0 + 9) div 2 = 4, e o elemento da posição 4 é 16. Como 23 > 16, a nova faixa começa em 5.
2. Faixa de 5 a 9: meio = (5 + 9) div 2 = 7, e o elemento é 56. Como 23 < 56, a nova faixa termina em 6.
3. Faixa de 5 a 6: meio = (5 + 6) div 2 = 5, e o elemento é 23. Achou.
4. Resultado: a busca binária faz 3 comparações. A busca sequencial faria 6, uma para cada posição de 0 a 5.

Ordenação. Os métodos simples de ordenação são três:

1. Bolha (bubble sort): percorre o vetor comparando cada par de vizinhos e troca o par fora de ordem. Ao fim de cada passagem, o maior elemento restante chega à última posição livre, como uma bolha que sobe. Com um aviso de "nenhuma troca nesta passagem", para cedo, e o melhor caso (vetor já ordenado) cai para O(n).
2. Seleção (selection sort): procura o menor elemento do trecho não ordenado e o troca com o primeiro desse trecho. Faz sempre o mesmo número de comparações, O(n²), mesmo com o vetor já ordenado, mas faz poucas trocas.
3. Inserção (insertion sort): pega cada elemento e o insere na posição certa entre os já ordenados à esquerda, como quem arruma cartas na mão. Com o vetor já ordenado, faz só n - 1 comparações (O(n)), e por isso é bom para vetores quase ordenados.

Os métodos eficientes usam a estratégia de dividir para conquistar, que divide o problema em partes menores, resolve cada parte e junta os resultados:

1. Merge sort (intercalação): divide o vetor ao meio até sobrar um elemento em cada parte e depois intercala as partes em ordem. É O(n log n) em todos os casos, mas precisa de memória auxiliar proporcional a n.
2. Quicksort: escolhe um elemento, o pivô, e separa os menores à esquerda e os maiores à direita; depois ordena cada lado do mesmo jeito. É O(n log n) no caso médio e O(n²) no pior caso, que ocorre quando o pivô é sempre o menor ou o maior elemento, como no vetor já ordenado com o pivô no extremo.
3. Heapsort: monta uma estrutura chamada heap, em que o maior elemento fica no topo, e retira o topo repetidas vezes. É O(n log n) em todos os casos e ordena no próprio vetor.

Um método é estável quando mantém a ordem original dos elementos de mesmo valor: bolha, inserção e merge sort são estáveis; seleção, quicksort e heapsort, nas versões comuns, não são. Um método é in-place quando ordena no próprio vetor, com memória extra fixa.

Exemplo resolvido: ordenar o vetor [5, 3, 8, 1] pelo método da bolha, em ordem crescente.

1. Primeira passagem: 5 e 3 trocam ([3, 5, 8, 1]); 5 e 8 ficam; 8 e 1 trocam ([3, 5, 1, 8]). O 8 chegou ao fim.
2. Segunda passagem: 3 e 5 ficam; 5 e 1 trocam ([3, 1, 5, 8]). O 5 chegou ao lugar.
3. Terceira passagem: 3 e 1 trocam ([1, 3, 5, 8]).
4. Resultado: o vetor fica [1, 3, 5, 8], depois de 3 passagens e 4 trocas.

Outros algoritmos que caem. Alguns algoritmos curtos aparecem em questões de teste de mesa:

1. Troca de duas variáveis: usa uma variável auxiliar (aux <- a, a <- b, b <- aux). Sem a auxiliar, o primeiro valor se perde.
2. Maior elemento de um vetor: guarda o primeiro elemento como maior e percorre o resto, trocando o maior quando acha um valor acima dele.
3. MDC de Euclides: o máximo divisor comum de a e b é o de b e do resto de a por b, até o resto dar zero. Para 48 e 18: 48 mod 18 = 12; 18 mod 12 = 6; 12 mod 6 = 0, e o MDC é 6.

Na prática, um tribunal mantém a lista de processos ordenada pelo número e usa busca binária para achar cada um. Para pôr poucos processos novos no lugar, a inserção é a escolha, porque a lista já está quase ordenada. Para reordenar a base pela data, o merge sort garante O(n log n) e, por ser estável, mantém a ordem anterior entre processos da mesma data.

A diferença que a banca mais troca é entre o quicksort e o merge sort: só o merge sort garante O(n log n) no pior caso, mas o quicksort ordena no próprio vetor. O erro comum é aplicar a busca binária a um vetor fora de ordem ou esquecer o caso base na recursão.

def f(n):
    if n <= 1:
        return 1
    return f(n - 1) + f(n - 2)

print(f(5))

Como a banca cobra: a banca pede a saída de uma função recursiva, o número de comparações de uma busca binária, o estado do vetor depois de uma passagem de um método de ordenação ou a complexidade e a estabilidade de cada método.

Quadros e comparações

A tabela abaixo compara as estruturas de repetição.

A tabela abaixo compara as formas de passagem de parâmetro.

A tabela abaixo reúne os métodos de ordenação.

Para decorar

Pegadinhas

Fontes e data

• [1] Conhecimento consolidado de livro didático de algoritmos e lógica de programação (características do algoritmo segundo Knuth, programação estruturada de Böhm e Jacopini, passagem de parâmetros, Portugol e VisuAlg, recursão, busca e ordenação).

Texto conferido em 15/10/2026.