Algoritmos iterativos

Terça, 28 de abril de 2020

Já aprendemos razoavelmente bem a linguagem de Python. Vimos como escrever programas que comandos sequenciais e condicionais if, comandos iterativos for e while e a organizar e chamar funções. Também vimos como declarar variáveis e criar listas. Nesta unidade, iremos explorar um pouco como utilizar tudo isso para resolver problemas, alguns mais simples, outros um pouco mais complicados.

Iterações simples e variáveis iteradoras

Vamos revisar alguns trechos de códigos triviais, mas vamos estudar um pouco mais os detalhes do que está acontecendo. Primeiro, vamos imprimir os 100 primeiros números inteiros.

for i in range(100):
    print(i)

Esse trecho usa diretamente o comando for, que é utilizado quando queremos percorrer sequências, no caso o intervalo range(100) que corresponde a uma sequência de números $0, 1, \dots, 99$. Essa é a maneira natural de resolver esse problema em Python, assim ela esconde uma série de detalhes sobre o nosso algoritmo.

Para entender o que o computador faz quando executamos um código como esse, é melhor reescrever o trecho de uma maneira equivalente, mas utilizando instruções mais simples, i.e., de mais baixo nível de abstração.

i = 0
while i < 100:
    print(i)
    i += 1

Agora podemos fazer várias observações. A variável i está intimamente ligada ao laço iterativo; como no exemplo ela conta o número de iterações executadas, damos a ela o nome de variável contadora. Podemos identificar partes relevantes que acessam ou modificam o valor de i.

  1. Inicialização. A variável contadora é inicializada em i = 0; inicializar significa associar um valor inicial adequado antes do primeiro uso.

  2. Condição. Testamos uma condição para continuar executando o laço em i < 100. Alguma vezes é útil pensar que o teste irá falhar apenas quando atingirmos uma condição desejada (ter impresso 100 números). Observe que imediatamente depois do laço, o valor de i é igual a 100.

  3. Atualização. A variável é atualizada com i += 1. Dentro do corpo do laço deve haver algum mecanismo para atualizar a variável contadora de forma que, em algum momento, a condição falhe.

A figura abaixo tem um código escrito em outra linguagem de programação. Você é capaz de identificar a inicialização, a condição e a atualização?

De maneira mais geral, podemos ter várias variáveis associadas a um laço. Como nem sempre essas variáveis contam o número de iterações executadas, costumamos chamá-las de variáveis acumuladoras, já que elas acumulam os resultados das operações de atualização. A seguinte função imprime as primeiras n potências na base dois.

def imprimir_potencias(n):
    i = 0
    pot = 0
    while i < 10:
        print(f"2^{i} = {pot}")
        i = i + 1
        pot = 2 * pot

Reflita sobre qual é o valor de i e pot imediatamente depois de terminado o laço.

Vamos tentar responder uma pergunta um pouco mais fundamental: será que um computador que tem operação de divisão é mais poderoso do que um que não tem? Para responder isso, vamos resolver um exercício rápido.

Calcule a divisão inteira de dois números usando apenas soma e subtração.

Aqui estamos deliberadamente limitando o nosso computador para não utilizar a operação de divisão. Primeiro, vamos escrever um algoritmo. A entrada são dois números, um $dividendo$ e um $divisor$.

  1. $residuo \gets dividendo$
  2. $contador \gets 0$
  3. Enquanto $residuo \geq divisor$:
    1. $residuo \gets residuo - divisor$
    2. $contador \gets contador + 1$
  4. Exiba $contador$

Repare que nesse pequeno algoritmo, temos uma variável acumuladora que decresce de valor. Reflita sobre a correção desse algoritmo e faça alguns testes pequenos para se convencer. Uma possível implementação em Python seria:

def divisao_inteira(dividendo, divisor):
    residuo = dividendo
    contador = 0
    while residuo >= divisor:
        residuo = residuo - divisor
        contador += 1
    return contador

Você poderia resolver esse problema usando um for ao invés de while?

Comandos iterativos aninhados

Eventualmente, queremos executar um comando iterativo no corpo de um outro comando iterativo. Na maioria das vezes, iremos lidar com duas variáveis contadoras simultaneamente. Por isso, é importante prestar atenção no nomes das variáveis e como e quando elas são alteradas.

Observe e procure entender o seguinte trecho:

def imprimir(m, n):
    for i in range(m):
        print(f"Linha {i}:", end="")
        for j in range(n):
            print(f" ({i},{j})", end="")
        print()

Essa função deve imprimir algo como

Linha 0: (0,0) (0,1) (0,2) (0,3)
Linha 1: (1,0) (1,1) (1,2) (1,3)
Linha 2: (2,0) (2,1) (2,2) (2,3)

Quando temos comandos iterativos aninhados como o anterior, normalmente falamos do laço externo e do laço interno. Iremos dizer que para cada valor fixado da variável i, percorremos com variável j. Vamos ver outro exemplo, uma pouco mais concreto, mas igualmente entediante:

media_provas = 0.0
for prova in range(1, 4):
    nota_prova = 0.0
    for questao in range(1, 11):
        print(f"Digite a nota questao {questao} da prova {prova}: ")
        nota_questao = float(input())
        nota_prova += nota_questao
    media_provas += nota_prova
media_provas = media_provas / 3.0
print(f"A média das provas foi {media_provas}")

Laços infinitos

Quando um programa executa indefinidamente um mesmo conjunto de instruções de um laço, então esse é um laço infinito. Por esse motivo, algumas vezes dizemos que o programa está ou entrou em loop. Isso ocorre por um erro no programa, que faz com que o laço nunca atinja a sua condição de parada. A causa pode ser um mero erro de digitação, ou alguma condição especial não tratada pelo algoritmo.

Vamos criar um programa para imprimir o triângulo como o abaixo, mas com $n$ linhas.

**********
*********
********
*******
******
*****
****
***
**
*

Um candidato a programa seria.

def triangulo(n):
    i = 1
    j = n
    while i <= n:
        i = 0
        while i < j:
            print('*', end="")
            i = i + 1
        print()
        j = j - 1

Esse programa imprime o triângulo desejado, mas continua executando indefinidamente. Se você quiser parar a execução terá que instruir o seu terminal a finalizar o processo, normalmente apertando-se as teclas CTRL + C no seu terminal. O problema não está na ideia do algoritmo, mas no fato de que reusamos uma variável para representar dois valores distintos! Descubra qual é esse erro, explique porque a condição de parada nunca é alcançada e corrija o programa.

Comandos não estruturados

Algumas vezes, a condição de parada escrita logo depois do comando while nunca é alcançada, mas o programa não entra em loop. Já vimos um caso desses, aqui está outro exemplo:

def ler_inteiro():
    while True:
        string_lida = input("Digite um número inteiro não negativo: ")
        if string_lida.isdigit():
            return int(string_lida)

Essa função insiste em ler um número do teclado até que o usuário digite uma entrada válida composta somente de números decimais. Repare que saímos do laço com um comando return. O mesmo efeito poderia ser utilizado com o comando break.

Uma atenção especial deve ser dada a esses comandos: break, continue, return (quando utilizado dentro de um laço). Eles são comandos não estruturados, o que significa que algumas das propriedades dos laços que normalmente esperaríamos não serão satisfeitas. Por exemplo, considere o trecho:

i = 1
while i < 10:
    print(f"Linha {i}:", end="")
    if i % 2 == 0:
        continue
    if i == 4:
        break
    for j in range(i):
        print(f" {j}", end="")
    print()
    i += 1

Esse programa entra em loop e tem um comportamento bem difícil de entender. O motivo é que a variável contadora não é atualizada em toda iteração. Para corrigir isso, mova a linha i += 1 para o início do corpo do laço. Qual o valor de i quando o programa termina? Tente determinar a saída desse programa.

Fauna

Vamos ver um problema um pouco mais interessante do que os anteriores — pelo menos um pouco mais animal.

Um coelho está a dois metros de sua esposa. Para chegar até ela, ele salta uma vez a cada minuto. Primeiro dá um saldo de um metro, depois de meio metro, depois de um quarto de metro e assim por diante. Em quanto tempo ele chegará até ela?

Parece fácil resolver esse problema. Basta uma variável acumuladora para guardar a distância percorrida e outra para guardar o tamanho do próximo passo. Tente resolver esse exercício. Eu escreveria o seguinte:

def tempo_gasto_coelho():
    numero_saltos = 0
    distancia = 0.0
    proximo_salto = 1.0

    while distancia < 2.0:
        numero_saltos += 1
        distancia += proximo_salto
        proximo_salto = proximo_salto / 2

    return numero_saltos

def main():
    tempo = tempo_gasto_coelho()
    print(f"O coelho gasta {tempo} minutos")

main()

Você já deve estar desconfiado — e com razão — de que esse programa tem algum erro. De fato, não faz muito tempo você deve ter aprendido a calcular soma de uma progressão geométrica. Nesse problema, a distância percorrida pelo coelho é dada pela soma dos inversos de $n$ potências na base dois,

$$ \mbox{distância} = 1 + \frac{1}{2} + \frac{1}{4} + \dots + \frac{1}{2^n}, $$

onde $n$ é o número de saltos do coelho. Se você tem boa memória, deve se lembrar de que essa soma é sempre menor que $2$ e só é igual a $2$ quando $n = \infty$. Parece razoável então supor que esse é mais um exemplo de programa que entra em laço infinito. Execute esse programa e explique o seu comportamento!

Vamos agora mudar de animal.

Uma tartaruga está a 22m de sua casa. No primeiro minuto, ela anda um metro, no segundo minuto, mais cansada, meio metro, no terceiro, um terço de metro e assim por diante. Em quanto tempo ela chegará até a casa?

Não é difícil modificar o programa anterior para calcular o tempo que a tartaruga irá gastar. Faça isso.

def tempo_gasto_tartaruga():
    numero_passo = 0
    distancia = 0
    proximo_passo = 0

    while distancia < 22:
        numero_passo += 1
        distancia += proximo_passo
        proximo_passo = 1.0 / numero_passo

    return numero_passo

Dessa vez, devemos esperar que o programa pare. Isso porque você já sabe ou irá aprender em breve que a soma da série harmônica diverge, isso é, para qualquer número real $D$, sempre existe um número $n$ tal que

$$ 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} > D. $$

Assim, existe um número $n_0$ para o qual a soma é maior do que $22$. Portanto, no momento que nossa função tempo_gasto_tartaruga tiver executado $n_0$ iterações, a condição do while irá falhar e o programa irá terminar.

Execute o programa acima e descubra e verifique se o programa realmente para e explique o comportamento do programa. Algumas vezes, quando estamos estudando um programa, é útil investigar como as variáveis contadoras e acumularas estão se modificando. Para isso usamos um debugger ou adicionamos instruções de impressão no corpo do código. Nesse exemplo, eu adicionaria as seguintes linhas no final do corpo do while:

        if numero_passo % 1000000 == 0:
            print(distancia)

Lendo e simulando código

Enquanto aprender a programar implica em aprender a escrever um programa, na maior parte do tempo em que estivermos programando vamos estar fazendo o inverso: lendo código. Os trechos de códigos que lemos algumas vezes são trechos de código que escrevemos recentemente, mas serão principalmente trechos de códigos escritos por outra pessoa, ou que nós mesmos escrevemos há muito tempo.

A razão para termos de ler programas são diversas. Em particular, lemos código porque ele não faz o que esperávamos que fizesse. Entre os motivos para isso ocorrer, já sabemos que estão os erros de programação, quando utilizamos instruções de maneira equivocada, ou erros de lógica, quando o algoritmo que projetamos não resolve o problema correspondente.

O nosso desafio é, portanto, descobrir um erro. Independente do tipo de erro, a principal ferramenta para identificá-lo é a simulação de código. Sabemos que ela pode ser feita de duas maneiras distintas

  1. Automaticamente, utilizando um debugger. Normalmente chamamos esse processo de depuração ou debugging.

  2. Manualmente, utilizando lápis e papel. Normalmente, chamamos esse processo de teste de mesa.

Vamos ver um exemplo:

def desenho(n):
    m = 2 * n - 1
    for i in range(n):
        j = 2 * i + 1
        for k in range((m-j)//2):
            print(" ", end="")
        for k in range(j):
            print("*", end="")
        print()

Para entender o que essa função faz, podemos usar a seguinte estratégia:

  1. Faça um teste de mesa. Use valores razoáveis para os dados da entrada. Por exemplo, se n = 1 então talvez não iremos simular todas as linhas de código; se n = 100, então o teste de mesa será muito lento e entediante e não iremos conseguir simular no papel. Usar n = 4 parece uma boa tentativa para essa função.

  2. Procure descrever em alto nível o que cada laço faz independentemente, ignorando os detalhes. Por exemplo, ao final do laço mais externo temos a impressão de uma quebra de linha, então sabemos que cada iteração corresponde a uma linha; o primeiro laço interno tem um único comando que imprime um espaço, então sabemo que esse laço imprime uma sequência de espaços, etc.

Usando essa estratégia, descreva o que essa função faz.

Desenhando na tela

Vamos criar um programa que desenha um disco na tela, usando caracteres, como o seguinte:

                    *
            * * * * * * * * *
        * * * * * * * * * * * * *
      * * * * * * * * * * * * * * *
    * * * * * * * * * * * * * * * * *
    * * * * * * * * * * * * * * * * *
  * * * * * * * * * * * * * * * * * * *
  * * * * * * * * * * * * * * * * * * *
  * * * * * * * * * * * * * * * * * * *
  * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * *
  * * * * * * * * * * * * * * * * * * *
  * * * * * * * * * * * * * * * * * * *
  * * * * * * * * * * * * * * * * * * *
  * * * * * * * * * * * * * * * * * * *
    * * * * * * * * * * * * * * * * *
    * * * * * * * * * * * * * * * * *
      * * * * * * * * * * * * * * *
        * * * * * * * * * * * * *
            * * * * * * * * *
                    *

Repare que o raio do disco é 10, então o número de linhas é 21. Antes de escrever um código, vamos pensar em um algoritmo simples em alto nível:

  1. para cada linha de $1$ até $2 * \text{RAIO} + 1$
    1. calcule o número de espaços para a linha
    2. calcule o número de asteriscos para linha
    3. imprima uma string de espaço
    4. imprima uma string de asteriscos com quebra de linha

Nem todos os passos estão bem definidos, então precisamos detalhar em como executar cada um dos passos. Vamos arriscar escrever o algoritmo principal e deixar os detalhes para depois.

RAIO = 10

def desenhar_disco():
    for linha in range(2 * RAIO + 1):
        num_espaco = calcular_num_espacos(linha)
        num_asterisco = calcular_num_asteriscos(linha)
        str_espaco = "  " * num_espaco
        str_asterisco = "* " * num_asterisco
        print(str_espaco, end="")
        print(str_asterisco, end="")
        print()

Enquanto o algoritmo é bem simples, pulamos a definição de duas funções importantes. Executar essas instruções não é uma tarefa trivial e, para isso precisamos de algum conhecimento em geometria e alguma paciência. Com um pouco de álgebra, descobrimos o número de asteriscos em uma linha e depois o número de espaços. Você não precisa se preocupar em como chegar nessas contas se não quiser.

def calcular_num_asteriscos_eixo(linha):
    y = RAIO - linha
    x = math.sqrt(RAIO ** 2 - y ** 2)
    return int(x)

def calcular_num_asteriscos(linha):
    return 2 * calcular_num_asteriscos_eixo(linha) + 1

def calcular_num_espacos(linha):
    return RAIO - calcular_num_asteriscos_eixo(linha)

Teste esse programa. Enquanto nosso algoritmo funciona e resolve a tarefa, a solução é bem insatisfatória. Parece muito difícil ter que pensar em tantos detalhes e, se quisermos mudar a figura geométrica, teremos que escrever outro algoritmo completamente diferente.

Para criar um programa um pouco mais simples e mais fácil de modificar, podemos tentar resolver a mesma tarefa com um algoritmo diferente. Olhar para para um mesmo problema por diferentes perspectivas pode nos trazer algoritmos mais simples.

Podemos interpretar a tela do computador como uma tela de pintura. Assim, cada espaço na tela representa um lugar ou uma célula onde não pintamos e cada asterisco uma célula que pintamos. Além disso, vamos imaginar que temos um sistema de coordenadas, como na figura:

Com isso, tudo que precisamos fazer é percorrer toda a tela e imprimir asterisco ou espaço, dependendo se a célula deve ou não ser pintada. Repare que podemos batizar cada célula da figura com um par de números $(i,j)$ correspondente à abscissa e à ordenada do nosso sistema de coordenadas. Criamos o seguinte programa:

RAIO = 10

def esta_disco(i, j):
    """Devolve true se (i,j) estiver
    no disco"""
    return i ** 2 + j ** 2 <= RAIO ** 2

def desenhar_disco2():
    for i in range(-RAIO, RAIO + 1):
        for j in range(-RAIO, RAIO + 1):
            no_disco = esta_disco(i, j)
            if no_disco:
                print("* ", end="")
            else:
                print("  ", end="")
        print()

Comparando com o algoritmo anterior, embora a função desenhar_disco2 tenha dois laços aninhados, ela parece mais simples de entender. Mais importante, é mais fácil modificá-la. Modifique o programa para que ele desenhe uma elipse ao invés de um disco. Depois experimente desenhar outras figuras geométricas.

Ordenação

Em seguida, vamos tratar de um problema clássico em Computação.

Escreva uma função que recebe uma lista de números inteiros e ordene-os de maneira crescente.

Comparando elementos

De maneira um pouco mais geral, estamos interessados em estudar algoritmos para ordenar conjuntos de elementos. Esses elementos podem ser de vários tipos. A única restrição que fazemos sobre eles é que possamos compará-los:

  • números reais,
  • nomes de pessoas,
  • times de futebol... :)

Poder comparar significa que dados dois elementos, podemos dizer se um é menor do que o outro. Para ser um pouco mais preciso, uma comparação $\le$ é uma relação entre os elementos de um conjunto $A$ de forma que dados dois elementos quaisquer $x , y \in A$, podemos decidir se $x \le y$ ou não.

Isso é bastante claro para números reais, afinal basta compararmos de acordo com a reta real. Mas isso não é claro se formos trabalhar com números complexos. Vamos fazer alguns testes. Em Python, podemos escrever um número imaginário adicionando o prefixo j ao número. Faça o seguinte em um console Python e tente experimentar com números reais, números complexos e comparações.

>>> inteiro_x = 23
>>> flutuante_y = 3.6
>>> inteiro_x <= flutuante_y
False
>>> complexo_w = 1j
>>> complexo_w ** 2
(-1+0j)
>>> complexo_z = 1 - 3j
>>> complexo_w <= complexo_z
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: '<=' not supported between instances of 'complex' and 'complex'
>>> complexo_w <= flutuante_y
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: '<=' not supported between instances of 'complex' and 'float'

Para comparar nomes de pessoas queremos comparar strings. Não é tão evidente como comparar duas strings assim como comparar dois números. Para isso, precisamos entender como uma string é representada em memória: uma string é uma sequência de caracteres e um caractere é representado por um ou mais bytes. Esses bytes representam números em uma grande tabela padronizada chamada Unicode, assim, se compararmos duas strings com exatamente um caractere cada uma, basta comparar os números correspondentes.

>>> caractere_a = 'a'
>>> ord(caractere_a)
97
>>> chr(97)
'a'
>>> caractere_b = 'B'
>>> ord(caractere_b)
66
>>> caractere_a <= caractere_b
False

Perceba que o caractere 'B' maiúsculo vem antes do caractere 'a' minúsculo porque o código dos caracteres maiúsculos vêm antes na tabela. Uma vez que sabemos comparar dois caracteres, podemos compara caractere por caractere lexicograficamente usando a mesma estratégia dos dicionários. Tente ordenar as palavras abaixo lexicograficamente e depois verifique a sua ordenação usando o console Python.

Zumbi
zebra
zumba
tumba
almanaque
alma

Da mesma maneira que podemos ordenar strings lexicograficamente, Python permite comparar listas. Existem algumas restrições no entanto, a principal delas é que possamos comparar os elementos das listas individualmente. Experimente:

>>> lista_x = [1, 2, 3]
>>> lista_y = [0.4, 100.0, 200, 1000]
>>> lista_x < lista_y
False
>>> lista_z = [1, 2, 3j]
>>> lista_x < lista_z
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: '<' not supported between instances of 'int' and 'complex'

Finalmente, queremos comparar times de futebol. Obviamente Python não toma partido de nenhum time e sequer entende o que é um time de futebol. Para que possamos comparar então, precisamos duas coisas:

  1. como representar um time?
  2. como comparar duas dessas representações?

Por exemplo, pode ser que queremos representar os dados estatísticos do time em um campeonato. Se no campeonato a ordenação dos times dos melhores para os piores seguir a ordem de mais pontos, maior saldo de gols e menor número de cartões amarelos, podemos representar um time usando uma tupla:

$$ (-pontos, -saldo\_gols, cartoes\_amarelos) $$

Com isso, podemos usar o fato de que Python já sabe comparar tuplas de números e utilizar o operador nativo.

>>> flamingo = (-15, -10, 3)
>>> botachamas = (-15, -10, 1)
>>> mangueiras = (-10, -12, 0)
>>> flamingo <= botachamas
False

Porque utilizamos números negativos? Quem é o primeiro colocado entre os três times anteriores?

É claro que dependendo do campeonato, a ordenação será diferente. Mais do que isso, pode ser que queremos ordenar times de maneira geral, assim vamos representar um time apenas por uma string contendo o nome do time. Como não queremos ordenar os times por ordem alfabética, não podemos mais utilizar o operador <= de Python. Por isso, precisamos de algum mecanismo alternativo para decidir se um elemento vem antes de outro elemento.

O mecanismo que normalmente adotamos é criar uma função comparar que recebe dois argumentos x e y e simula o papel da x <= y. Assim comparar(x,y) é True sempre que x <= y. Repare que definimos apenas um operador correspondendo a <=, mas se quisermos saber ser x > y então bastaria escrever not comparar(x,y).

Dada a natureza subjetiva de comparação de times, cada torcedor teria critérios diferentes para comparar seus times. Por exemplo, um flaminguista pode acreditar que seu time vem antes de qualquer outro e que todos os outros são iguais. Ele escreveria:

def comparar_times(time_x, time_y):
    if time_x == time_y:
        return True
    elif time_y == 'Flamingo':
        return False
    else:
        return True

Experimente passando vários argumentos distintos e tente explicar o comportamento dessa função.

A discussão anterior deve ter deixado claro que a relação de comparação é apenas um conceito abstrato e a maneira como implementamos essa comparação é indiferente para os algoritmos de ordenação.

Algoritmos de ordenação

Existem várias estratégias para ordenar uma lista de números. Vamos estudar três estratégias, que levam a três algoritmos distintos.

  1. Percorrer os elementos dois a dois e trocar pares de elementos fora de ordem e continuar esse processo até que todos estejam ordenados. Já vimos o algoritmo que faz isso, que é o algoritmo ordenação da bolha ou bubble sort.

  2. Selecionar o menor elemento e trocá-lo com o primeiro e repetir esse processo com os demais. Esse é o algoritmo de ordenação por seleção ou selection sort.

  3. Percorrer os elementos e inserir cada um deles na posição correta. Esse é o algoritmo de ordenação por inserção ou insertion sort.

Ordenação da bolha

Já vimos o algoritmo de ordenação da bolha. Vamos reescrever o algoritmo em português, dessa vez em mais alto nível.

  1. Repita $n-1$ vezes:
    1. Para cada índice $i$ do primeiro ao penúltimo
      1. Compare o elemento de $i$ com o de $i+1$
      2. Se estiverem fora de ordem, troque-os

Com o algoritmo escrito, fica fácil escrever uma função em Python.

def bubble_sort(lista):
    n = len(lista)
    for _ in range(n-1):
        for i in range(n - 1):
            if lista[i] > lista[i+1]:
                aux = lista[i]
                lista[i] = lista[i+1]
                lista[i+1] = aux

As últimas três linhas realizam a troca dos elementos. Elas são instruções bem simples, então dificilmente alguma programadora iria convertê-las em uma função em um código real. Na nossa discussão, poderia ser mais claro se pudéssemos dizer trocar(lista, i, i+1), então vamos reescrever nossa função por apelo a clareza.

def trocar(lista, i, j):
    aux = lista[i]
    lista[i] = lista[j]
    lista[j] = aux

def bubble_sort(lista):
    n = len(lista)
    for _ in range(n-1):
        for i in range(n - 1):
            if lista[i] > lista[i+1]:
                trocar(lista, i, i+1)

Nunca devemos nos esquecer de testar. Façamos isso adicionando e executando.

def main():
    lista = [3, 5, 2, 0, 9, 6]
    bubble_sort(lista)
    print(lista)

main()

Ordenação por seleção

O algoritmo de ordenação por seleção pode ser resumido como colocar cada item no seu devido lugar. Assim, primeiro colocamos o primeiro elemento na primeira posição, em seguida colocamos o segundo elemento na segunda posição e assim por diante.

Pode ser útil colorir a lista em duas cores: uma parte verde no início da lista que já contém todos os elementos ordenados e uma parte preta, que contém os demais elemento, todos eles maiores do que os elementos na lista verde. Portanto, para aumentar o tamanho da parte verde da lista, basta encontrar a posição do menor elemento da lista preta e trocá-lo de posição com o primeiro elemento da lista preta.

Veja a animação a seguir que exemplifica a execução desse algoritmo. Para animar, clique na figura e segure as setas para direita ou para a esquerda.

Já podemos escrever o algoritmo em português. No algoritmo a seguir, iremos falar de lista preta. Para deixar esse termo preciso, iremos dizer que a lista preta é a parte da lista original que começa no índice $i$ e vai até o último índice.

  1. para cada índice $i$ do primeiro até o último
    1. encontrar o menor elemento da lista preta
    2. troque esse elemento com o primeiro da lista preta

Simples, claro e conciso. Agora podemos implementar; como sempre, iremos utilizar stubs para simplificar o processo de desenvolvimento.

def encontrar_indice_menor(lista, i):
    """Devolve o índice do menor elemento em lista[i:]"""
    pass

def selection_sort(lista):
    for i in range(len(lista)):
        indice_menor = encontrar_indice_menor(lista, i)
        trocar(i, indice_menor)

Uma pergunta, o que acontece quando i corresponde ao último índice da lista?

Uma observação é importante. Para que possamos trocar dois elementos da lista com a função trocar, precisamos do índice onde está o menor elemento da lista preta, não o valor. Agora implementemos o stub.

def encontrar_indice_menor(lista, i):
    """Devolve o índice do menor elemento em lista[i:]"""
    indice_menor = i
    for j in range(i, len(lista)):
        if lista[j] < lista[indice_menor]:
            indice_menor = j
    return indice_menor

Não foi muito mais difícil do que encontrar o mínimo a lista inteira. Você viu como é muito mais simples utilizar funções, sempre nos preocupamos com tarefas pequeninas. Mas com a experiência, a maioria dos programadores iria escrever todas as instruções do algoritmo diretamente no corpo de selection_sort. Tente fazer isso. Claro, não deixe de testar sua função adicionando uma chamada na função main.

Ordenação por inserção

Para explicar o algoritmo de inserção, pode ser útil fazer um exercício de pensamento. Imagine você com um baralho de cartas. Para ordenar, você coloca o deck de cartas do lado esquerdo da mesa e pega a carta do topo, uma por vez. A cada carta retirada, vc insere em um novo deck de cartas do lado direito da mesa, já na posição correta. É claro que no final, todas as cartas estarão ordenadas no deck da direita.

Enquanto essa intuição é simples, não queremos utilizar esse algoritmo. O motivo é que não queremos criar duas listas simplesmente para ordenar os elementos. Usar duas listas, além de gastar mais memória e mais tempo de execução, é completamente desnecessário para esse algoritmo. Para utilizar apenas uma lista, vamos de novo pintá-lo com duas cores: uma parte verde ordenada e outra preta com os demais elementos.

Vamos escrever o algoritmo. Mais uma vez, vamos usar $i$ para representar o início da lista preta e dizer que a lista verde é a parte da lista do primeiro elementos até o último antes de $i$.

  1. para índice $i$ do segundo até o último:
    1. $chave \gets lista[i]$
    2. encontre a posição de inserção $j$ de $chave$ na lista verde
    3. desloque para direita os elementos do índice $j$ até $i - 1$
    4. $lista[j] \gets chave$

De novo, temos algumas instruções ainda não completamente especificadas. Vamos escrever o algoritmo usando stubs. Vamos aproveitar a descrição dos passos do nosso algoritmo para documentar essas funções.

def encontrar_posicao(lista, i, chave):
    """
    devolve a posição de inserção de chave em lista[:i]
    """
    pass


def deslocar_lista(lista, i, j):
    """
    desloca para direita os elementos de lista
    do índice j até i-1
    """
    pass

def insertion_sort(lista):
    for i in range(1, len(lista)):
        chave = lista[i]
        j = encontrar_posicao(lista, i, chave)
        deslocar_lista(lista, i, j)
        lista[j] = chave

Agora não deve ser difícil implementar cada subtarefa independentemente. Fazemo-lo!

def encontrar_posicao(lista, i, chave):
    """
    devolve a posição de inserção de chave em lista[:i]
    """
    j = 0
    while j != i and chave > lista[j]:
        j += 1
    return j


def deslocar_lista(lista, i, j):
    """
    desloca para direita os elementos de lista
    do índice j até i-1
    """
    k = i
    while k > j:
        lista[k] = lista[k-1]
        k -= 1

Vamos refletir um pouco sobre esse algoritmo. Em cada iteração, queremos descobrir em qual posição j da lista verde iremos inserir o valor de chave. Assim, percorremos do primeiro até o índice j. Depois, temos que deslocar a parte da lista de j até o índice i-1. Isso significa que devemos acessar todos os elementos da lista verde em toda iteração! Faça o seguinte, com essa preocupação em mente, tente simular o algoritmo de ordenação por inserção para a seguinte lista:

lista = [1, 2, 3, 5, 4, 6, 8, 7]

Simule todos os passos na mão. Tente descobrir uma melhoria nesse algoritmo de forma a evitar ter de percorrer toda a lista verde em toda iteração! Implemente essa melhoria, dessa vez sem utilizar sub-rotinas.