📊 Ordenação, Dicionários e Tuplas

Seção 6.16–6.19 — Bubble Sort, dicionários e tuplas

🫧 6.16 Ordenação

Até agora, os elementos de nossas listas aparecem na mesma ordem em que foram digitados, sem qualquer ordenação. Para ordenar uma lista, realizaremos uma operação semelhante à da pesquisa, mas trocando a ordem dos elementos quando necessário. Um algoritmo muito simples de ordenação é o Bubble Sort (método das bolhas).

A ordenação pelo método das bolhas consiste em comparar dois elementos a cada vez. Se o valor do primeiro elemento for maior que o do segundo, eles trocam de posição. Essa operação é repetida para o próximo elemento até o fim da lista. Utilizaremos um marcador para saber se chegamos ao fim da lista trocando ou não algum elemento — essa propriedade garante que o maior elemento vá para a última posição da lista, ou seja, sua posição correta. Isso permite eliminar um elemento do fim da lista a cada passagem completa.

Listagem 6.44 — Ordenação pelo método das bolhasL=[7,4,3,12,8]
fim=5
while fim > 1:
    trocou=False
    x=0
    while x<(fim-1):
        if L[x] > L[x+1]:
            trocou=True
            temp=L[x]
            L[x]=L[x+1]
            L[x+1]=temp
        x+=1
    if not trocou:
        break
    fim-=1
for e in L:
    print(e)

A troca de valores entre duas variáveis utiliza uma variável auxiliar temporária (temp) para armazenar o valor de uma delas durante a troca — como trocar o conteúdo de duas xícaras usando uma terceira. Quando nenhuma troca acontece em uma passagem completa (not trocou), a lista já está ordenada e o algoritmo termina com break.

Exercício 6.14

O que acontece quando a lista já está ordenada? Rastreie o programa da Listagem 6.44, mas com a lista L=[1,2,3,4,5].

Exercício 6.15

O que acontece quando dois valores são iguais? Rastreie o programa da listagem 6.44, mas com a lista L=[3,3,1,5,4].

Exercício 6.16

Modifique o programa da listagem 6.44 para ordenar a lista em ordem decrescente. L=[1,2,3,4,5] deve ser ordenada como L=[5,4,3,2,1].

📖 6.17 Dicionários

Dicionários consistem em uma estrutura de dados similar às listas, mas com propriedades de acesso diferentes. Um dicionário é composto por um conjunto de chaves e valores. O dicionário em si consiste em relacionar uma chave a um valor específico.

Em Python, criamos dicionários utilizando chaves ({}). Cada elemento do dicionário é uma combinação de chave e valor. Vejamos um exemplo onde os preços de mercadorias seguem a tabela a seguir:

Listagem 6.45 — Criação de um dicionáriotabela = { "Alface": 0.45,
           "Batata": 1.20,
           "Tomate": 2.30,
           "Feijão": 1.50 }

Um dicionário é acessado por suas chaves. Para obter o preço da alface, digitamos no interpretador tabela["Alface"]. Diferentemente de listas, onde o índice é um número, dicionários utilizam suas chaves como índice. Quando atribuímos um valor a uma chave, duas coisas podem ocorrer: (1) se a chave já existe, o valor associado é alterado; (2) se a chave não existe, a nova chave será adicionada ao dicionário.

Listagem 6.46 — Funcionamento do dicionário>>> tabela = { "Alface": 0.45,
...            "Batata": 1.20,
...            "Tomate": 2.30,
...            "Feijão": 1.50 }
>>> print(tabela["Tomate"])
2.3
>>> print(tabela)
{'Batata': 1.2, 'Alface': 0.45, 'Tomate': 2.3, 'Feijão': 1.5}
>>> tabela["Tomate"] = 2.50
>>> print(tabela["Tomate"])
2.5
>>> tabela["Cebola"] = 1.20
>>> print(tabela)
{'Batata': 1.2, 'Alface': 0.45, 'Tomate': 2.5, 'Cebola': 1.2, 'Feijão': 1.5}

Outra diferença entre dicionários e listas é que, ao utilizarmos dicionários, perdemos a noção de ordem. Se a chave não existir, uma exceção do tipo KeyError será ativada (Listagem 6.47):

Listagem 6.47 — Acesso a uma chave inexistente>>> tabela = { "Alface": 0.45,
...            "Batata": 1.20,
...            "Tomate": 2.30,
...            "Feijão": 1.50 }
>>> print(tabela["Manga"])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 'Manga'

Para verificar se uma chave pertence ao dicionário, podemos usar o operador in. Para obter uma lista das chaves ou valores associados, usamos os métodos .keys() e .values() (Listagens 6.48 e 6.49):

Listagem 6.48 — Verificação da existência de uma chave>>> tabela = { "Alface": 0.45,
...            "Batata": 1.20,
...            "Tomate": 2.30,
...            "Feijão": 1.50 }
>>> print("Manga" in tabela)
False
>>> print("Batata" in tabela)
True

Listagem 6.49 — Obtenção de uma lista de chaves e valores>>> tabela = { "Alface": 0.45,
...            "Batata": 1.20,
...            "Tomate": 2.30,
...            "Feijão": 1.50 }
>>> print(tabela.keys())
dict_keys(['Batata', 'Alface', 'Tomate', 'Feijão'])
>>> print(tabela.values())
dict_values([1.2, 0.45, 2.3, 1.5])

Observe que os métodos keys() e values() retornam geradores. Você pode utilizá-los diretamente dentro de um for ou transformá-los em lista usando a função list. Vejamos um programa que utiliza dicionários para exibir o preço de um produto (Listagem 6.50):

Listagem 6.50 — Obtenção do preço com um dicionáriotabela = { "Alface": 0.45,
           "Batata": 1.20,
           "Tomate": 2.30,
           "Feijão": 1.50 }
while True:
    produto=input("Digite o nome do produto, fim para terminar:")
    if produto == "fim":
        break
    if produto in tabela:
        print("Preço %5.2f" % tabela[produto])
    else:
        print("Produto não encontrado!")

Para apagar uma chave, utilizaremos a instrução del (Listagem 6.51):

Listagem 6.51 — Exclusão de uma associação do dicionário>>> tabela = { "Alface": 0.45,
...            "Batata": 1.20,
...            "Tomate": 2.30,
...            "Feijão": 1.50 }
>>> del tabela["Tomate"]
>>> print(tabela)
{'Batata': 1.2, 'Alface': 0.45, 'Feijão': 1.5}

💡 Quando usar dicionários vs. listas? Se seus dados são acessados por suas chaves (nomes, códigos), quase nunca você precisa acessa-los por índice numérico e você precisa pesquisar rapidamente, um dicionário é mais interessante. Listas preservam a ordem de inserção e são melhores quando índices numéricos são necessários.

🗄️ 6.18 Dicionários com listas

Em Python, podemos ter dicionários nos quais as chaves são associadas a listas ou mesmo a outros dicionários. Imagine uma relação de estoque de mercadorias onde, além do preço, a quantidade em estoque (Listagem 6.52):

Listagem 6.52 — Dicionário com listasestoque = { "tomate": [ 1000, 2.30],
            "alface": [ 500, 0.45],
            "batata": [ 2001, 1.20],
            "feijão": [ 100, 1.50] }

Nesse caso, o nome do produto é a chave, e a lista consiste nos valores associados a essa chave. O primeiro elemento da lista é a quantidade disponível; o segundo, o preço do produto. Uma aplicação mais completa processa uma lista de operações e calcula o preço total de vendas, atualizando também a quantidade em estoque (Listagem 6.53):

Listagem 6.53 — Dicionário com estoque e operações de vendaestoque = { "tomate": [ 1000, 2.30],
            "alface": [ 500, 0.45],
            "batata": [ 2001, 1.20],
            "feijão": [ 100, 1.50] }
venda = [ ["tomate", 5], ["batata", 10], ["alface",5] ]
total = 0
print("Vendas:\n")
for operação in venda:
    produto, quantidade = operação
    preço = estoque[produto][1]
    custo = preço * quantidade
    print("%12s: %3d x %6.2f = %6.2f" %
          (produto, quantidade,preço,custo))
    estoque[produto][0] -= quantidade
    total+=custo
print(" Custo total: %21.2f\n" % total)
print("Estoque:\n")
for chave, dados in estoque.items():
    print("Descrição: ", chave)
    print("Quantidade: ", dados[0])
    print("Preço: %6.2f\n" % dados[1])

Utilizamos uma operação de desempacotamento, como já fizemos com for e enumerate. Como operação é uma lista com dois elementos, ao escrevermos produto, quantidade = operação temos o primeiro elemento de operação atribuído a produto, e o segundo, a quantidade. Em seguida, utilizamos o conteúdo de produto como chave no dicionário estoque. O método .items() retorna pares de chave-valor como tuplas, permitindo percorrer todo o dicionário com for.

Exercício 6.17

Altere o programa da listagem 6.53 de forma a solicitar ao usuário o produto e a quantidade vendida. Verifique se o nome do produto digitado existe no dicionário, e só então efetue a baixa em estoque.

Exercício 6.18

Escreva um programa que gere um dicionário, onde cada chave seja um caractere, e seu valor seja o número desse caractere encontrado em uma frase lida. Exemplo: O rato -> { "O":1, "r":1, "a":1, "t":1, "o":1}

📦 6.19 Tuplas

Tuplas podem ser vistas como listas em Python, com a grande diferença de serem imutáveis. Tuplas são ideais para representar listas de valores constantes e também para realizar operações de empacotamento e desempacotamento de valores.

Tuplas são criadas de forma semelhante às listas, mas utilizamos parênteses em vez de colchetes. Tuplas suportam a maior parte das operações de lista, como fatiamento e indexação:

>>> tupla = ("a", "b", "c")
>>> tupla
('a', 'b', 'c')
>>> tupla[0]
'a'
>>> tupla[2:]
('b', 'c')
>>> tupla * 2
('a', 'b', 'c', 'a', 'b', 'c')
>>> len(tupla)
3

Mas tuplas não podem ter seus elementos alterados. Veja o que acontece se tentarmos alterar uma tupla:

>>> tupla[0]="A"
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment

Várias funções utilizam ou geram tuplas em Python. Tuplas podem ser utilizadas com for:

>>> for elemento in tupla:
...     print(elemento)
a
b
c

Python também permite criar tuplas usando valores separados por vírgula, independente de usarmos parênteses. Esse tipo de operação é chamado de empacotamento:

>>> tupla = 100, 200, 300
>>> tupla
(100, 200, 300)

Tuplas também podem ser utilizadas para desempacotar valores. O primeiro valor, 10, foi atribuído à primeira variável, e 20 à segunda. Esse tipo de construção é interessante para distribuirmos o valor de uma só tupla em várias variáveis:

>>> a, b = 10, 20
>>> a
10
>>> b
20

Também podemos trocar rapidamente os valores de variáveis com construções de uma tupla:

>>> a, b = 10, 20
>>> a, b = b, a
>>> a
20
>>> b
10

A sintaxe do Python é um tanto especial quando precisamos criar tuplas com apenas um elemento. Como os valores são escritos entre parênteses, quando apenas um valor estiver presente, devemos acrescentar uma vírgula após o valor para indicar que o valor é uma tupla:

>>> t1 = (1)
>>> t1
1
>>> t2 = (1,)
>>> t2
(1,)
>>> t3 = 1,
>>> t3
(1,)

Podemos também criar tuplas vazias, escrever apenas os parênteses, e tuplas a partir de listas usando a função tuple:

>>> t4 = ()
>>> t4
()
>>> len(t4)
0
>>> L = [1,2,3]
>>> T = tuple(L)
>>> T
(1, 2, 3)

Observe que se uma tupla contiver uma lista ou outro objeto que pode ser alterado, este continuará a funcionar normalmente. Ou seja, a tupla em si é imutável, mas os objetos dentro dela podem ser alteráveis:

>>> tupla=('a', ['b', 'c', 'd'])
>>> len(tupla)
2
>>> tupla[1]
['b', 'c', 'd']
>>> tupla[1].append("e")
>>> tupla
('a', ['b', 'c', 'd', 'e'])

💡 Neste caso, nada mudou na tupla em si, mas na lista que é seu segundo elemento. Ou seja, a tupla não foi alterada, mas a lista que ela continha, sim. As tuplas são amplamente utilizadas em Python para retornar múltiplos valores de funções e para desempacotamento de dados.