Organização de dados, análise de operações, implementação de algoritmos eficientes, buscas lineares e binárias, avaliação de complexidade com notação Big O e ordenação com Bubble Sort em arrays.
A "list comprehension" é uma forma concisa e elegante de criar listas em Python. A sintaxe é mais curta e, muitas vezes, mais legível do que usar um loop `for` tradicional com `append`.
Por que este código?
Utilizamos o método `char.isspace()` que é mais robusto do que `char != ' '`. Ele identifica todos os tipos de caracteres de espaço em branco, incluindo espaços, tabulações (`\t`) e quebras de linha (`\n`), garantindo uma filtragem completa e precisa conforme solicitado.
A proposta desse exercício 2, à primeira vista, suscita reflexões interessantes sobre restrições de acesso a dados e seus impactos na complexidade de algoritmos. Quando transposto para execução manual — ordenar um pequeno baralho sob regras rígidas de manipulação — o problema se revela mais profundo: o algoritmo resultante apresenta, de forma inevitável, uma complexidade quadrática $O(n^2)$.
Essa constatação não decorre de detalhes de implementação, mas das próprias restrições impostas: acesso sequencial às cartas, movimentação unitária e inserção apenas nas extremidades. Em ciência da computação, tais limitações equivalem ao uso de pilhas e deques, estruturas que impedem a aplicação de métodos mais eficientes como Quicksort ou Mergesort. O resultado é um processo que se aproxima conceitualmente de algoritmos clássicos como Insertion Sort e Selection Sort, ambos notoriamente quadráticos no pior caso.
Esse modelo de acesso restrito inviabiliza algoritmos mais sofisticados, que dependem de acesso aleatório ou de divisão eficiente de listas.
Dentro dessas limitações, o processo lembra dois métodos conhecidos:
Cada carta retirada de A deve ser colocada em sua posição correta em uma pilha auxiliar (B/C/D). No pior caso, inserir exige deslocar todas as cartas de uma pilha, resultando no custo acumulado: $1 + 2 + \dots + n = O(n^2)$
Outra estratégia é escolher, a cada rodada, a menor carta restante e transferi-la para a pilha final. Encontrar a menor implica percorrer todas as n cartas restantes, repetido n vezes: $n + (n-1) + (n-2) + \dots + 1 = O(n^2)$
Para ilustrar, segue uma simulação didática que respeita as restrições descritas:
from collections import deque
# ============================================
# Procedimento operacional (amarrado às regras)
# ============================================
# Regras do enunciado (mapeamento):
# (a) Todas as cartas começam em A (a "mão") -> representamos como deque A
# (b) Objetivo: ordenar as 13 cartas -> retornamos a lista ordenada
# (c) Só pode pegar a PRIMEIRA carta de uma lista -> popleft()
# (d) Pode inserir no INÍCIO ou FIM de uma lista -> appendleft() / append()
# (e) No máximo 4 listas -> usamos A, B, C (D não é necessário)
# (f) Pode inverter uma lista movendo para outra -> (neste método, a inversão aparece
# naturalmente ao usar C como buffer)
def mover_primeira(origem, destino, posicao="inicio"):
"""
Operação atômica permitida:
- Remove a primeira carta (topo) de 'origem' e insere no início ou fim de 'destino'.
"""
carta = origem.popleft() # (c)
if posicao == "inicio":
destino.appendleft(carta) # (d)
else:
destino.append(carta) # (d)
def ordenar_13_cartas(cartas):
"""
Estratégia: INSERTION SORT usando 3 listas (A, B, C), respeitando (c) e (d).
Invariante:
B permanece SEMPRE ordenada do menor (frente) ao maior (fim).
Passo de inserção de uma carta x:
1) tire x do topo de A
2) enquanto a primeira de B for menor que x:
mova a primeira de B para o INÍCIO de C (isso inverte a ordem dos removidos)
3) coloque x no INÍCIO de B (antes do primeiro >= x)
4) devolva tudo de C para o INÍCIO de B (desfaz a inversão e restaura a ordem)
"""
A = deque(cartas) # (a) topo = esquerda
B = deque() # lista ordenada
C = deque() # buffer (auxiliar)
while A:
x = A.popleft() # (c) pega a primeira carta de A
# Move cartas menores para C (inverte)
while B and B[0] < x:
mover_primeira(B, C, "inicio")
# Insere x no lugar correto (antes do primeiro >= x)
B.appendleft(x)
# Restaura as cartas movidas (desfaz a inversão)
while C:
mover_primeira(C, B, "inicio")
# Se você quiser "devolver" para uma mão A_final com topo = menor carta:
A_final = deque()
while B:
mover_primeira(B, A_final, "fim") # preserva a ordem ascendente em A_final
return list(A_final)
# Demonstração
cartas = [7, 2, 11, 1, 9, 4, 13, 5, 8, 3, 12, 6, 10]
print(ordenar_13_cartas(cartas))
# Saída esperada: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
# Complexidade (por que é O(n^2)):
# Para cada carta retirada de A, no pior caso movemos várias cartas de B para C e de volta.
# Isso dá um número total de movimentos proporcional a 1 + 2 + ... + (n-1) = O(n^2).
O processo pode ser dividido em duas fases:
As restrições impostas pelo problema conduzem inevitavelmente a um algoritmo de complexidade $O(n^2)$ no pior caso. Mesmo com otimizações de implementação (como o uso de deque para inserções em tempo constante nas extremidades), o limite teórico permanece.
Esse comportamento aproxima o exercício de um Insertion Sort ou Selection Sort em ambiente restrito, demonstrando que a ineficiência não resulta da técnica escolhida, mas do modelo de acesso limitado que define as regras do jogo.
Escrevi um artigo sobre isso. Se tiver interesse acesse: aqui.
A busca linear é o método de busca mais simples. Ela percorre sequencialmente cada elemento do array, um por um, desde o início, até encontrar o valor desejado ou chegar ao final do array.
Portanto, seriam necessários 4 passos para realizar a busca linear.
A busca binária é um algoritmo muito mais eficiente, mas requer que o array esteja ordenado. A cada passo, ela elimina metade dos elementos restantes, comparando o alvo com o elemento do meio da seção de busca.
Neste caso específico e favorável, a busca binária levaria apenas 1 passo.
Vamos considerar um alvo diferente, como o número 12, para ilustrar melhor:
greatestNumber para ter uma complexidade de tempo linear.
A função original é O(N²) porque faz dois laços aninhados: para cada elemento i (N vezes),
ela percorre novamente o array inteiro para comparar com todos os j (mais N comparações).
Em termos práticos, o número de comparações cresce como N × N.
A versão otimizada elimina o laço interno mantendo um invariante:
após processar cada posição, greatest_so_far guarda o maior valor visto até agora.
Assim, fazemos apenas um passeio pela lista: tempo O(N) e espaço extra O(1).
Por que este código?
Ele percorre o array uma única vez. Começa assumindo que o primeiro elemento é o maior e, a cada novo elemento,
faz apenas uma comparação: “este número é maior do que o maior que eu já vi?”.
Se sim, atualiza greatest_so_far. Ao final, essa variável contém o maior valor do array.
Isso reduz o tempo de O(N²) para O(N).
Casos de borda recomendados para teste:
[5, 1, 5, 4, 4, 3], o maior número é 5, mas o maior número único é 3.
A solução abaixo continua em tempo O(N), mas usa memória extra O(N) para contar ocorrências.
Resumo de complexidade:
O número de grãos em cada quadrado segue uma progressão geométrica de base 2. O quadrado 1 tem $2^0=1$ grão, o quadrado 2 tem $2^1=2$ grãos, o quadrado 3 tem $2^2=4$ grãos, e assim por diante. O quadrado `n` terá $2^{(n-1)}$ grãos.
Para encontrar o número do quadrado (`n`) a partir da quantidade de grãos (`g`), precisamos resolver a equação $g = 2^{(n-1)}$. Isso é um problema de logaritmo.
A complexidade de tempo da função é $O(1)$, ou tempo constante.
Por quê? A função executa um número fixo de operações matemáticas (`math.log2`, adição, etc.), independentemente do tamanho do número de grãos de entrada. Seja para 16 grãos ou para um trilhão de grãos, o número de cálculos é o mesmo. Portanto, o tempo de execução não cresce com o tamanho da entrada, caracterizando a complexidade $O(1)$.
A complexidade de tempo desta função é $O(N)$, ou tempo linear, onde N é o número de strings no array de entrada.
O algoritmo solicitado é conhecido como Cocktail Shaker Sort. Ele é uma variação do Bubble Sort que otimiza o processo ordenando em ambas as direções em cada passagem. Em uma passagem, ele move o maior elemento para o final (como o Bubble Sort) e, na passagem de volta, move o menor elemento para o início. Isso pode resolver o problema de "tartarugas" (elementos pequenos no final da lista) que tornam o Bubble Sort lento.
# Supondo que a função está dentro de uma classe com self._a (o array)
# e self.swap(i, j) como no exercício original.
def bidirectionalBubbleSort(self):
left_index = 0
right_index = len(self._a) - 1
swapped = True
while swapped:
# Primeiro, passamos da esquerda para a direita (Bubble Sort padrão)
swapped = False
for i in range(left_index, right_index):
if self._a[i] > self._a[i+1]:
self.swap(i, i+1)
swapped = True
# Se nenhuma troca ocorreu, o array está ordenado.
if not swapped:
break
# O elemento na `right_index` agora é o maior, então podemos diminuir o limite
right_index = right_index - 1
# Agora, passamos da direita para a esquerda, movendo o menor para o início
swapped = False
for i in range(right_index, left_index, -1):
if self._a[i] < self._a[i-1]:
self.swap(i, i-1)
swapped = True
# O elemento na `left_index` agora é o menor, podemos aumentar o limite
left_index = left_index + 1
# Exemplo de como a classe poderia ser para teste:
class Sorter:
def __init__(self, arr):
self._a = arr
def swap(self, i, j):
self._a[i], self._a[j] = self._a[j], self._a[i]
bidirectionalBubbleSort = bidirectionalBubbleSort # Atribui a função à classe
# Teste
my_array = [5, 1, 4, 2, 8, 0, 3, 9, 6, 7]
sorter = Sorter(my_array)
sorter.bidirectionalBubbleSort()
print(sorter._a)
O Bubble Sort é um algoritmo de ordenação simples que repetidamente percorre a lista, compara elementos adjacentes e os troca se estiverem na ordem errada. As passagens pela lista são repetidas até que nenhuma troca seja necessária, o que indica que a lista está ordenada.
def bubble_sort_numeros(lista):
n = len(lista)
# Percorre todos os elementos da lista
for i in range(n):
# A flag `trocou` otimiza o algoritmo. Se não houver trocas em uma passagem,
# a lista já está ordenada e podemos parar.
trocou = False
# A última i posições já estão no lugar certo
for j in range(0, n-i-1):
# Percorre a lista da esquerda para a direita
# Troca se o elemento encontrado for maior que o próximo
if lista[j] > lista[j+1]:
lista[j], lista[j+1] = lista[j+1], lista[j]
trocou = True
if not trocou:
break
return lista
# --- Testes da Função ---
lista1 = [64, 34, 25, 12, 22, 11, 90]
lista2 = [5, 1, 4, 2, 8]
lista3 = [1, 2, 3, 4, 5] # Já ordenada
lista4 = [9, 8, 7, 6, 5] # Ordem reversa
lista5 = [] # Lista vazia
print(f"Lista original 1: {lista1}")
print(f"Lista ordenada 1: {bubble_sort_numeros(lista1.copy())}\n")
print(f"Lista original 2: {lista2}")
print(f"Lista ordenada 2: {bubble_sort_numeros(lista2.copy())}\n")
print(f"Lista original 3: {lista3}")
print(f"Lista ordenada 3: {bubble_sort_numeros(lista3.copy())}\n")
print(f"Lista original 4: {lista4}")
print(f"Lista ordenada 4: {bubble_sort_numeros(lista4.copy())}\n")
print(f"Lista original 5: {lista5}")
print(f"Lista ordenada 5: {bubble_sort_numeros(lista5.copy())}\n")
A beleza do Python é que a mesma lógica do Bubble Sort pode ser aplicada a strings sem modificação alguma. Os operadores de comparação (`>`, `<`, etc.) funcionam nativamente para strings, comparando-as em ordem lexicográfica (alfabética).
# A função é exatamente a mesma do exercício anterior.
# Vamos renomeá-la para clareza.
def bubble_sort_strings(lista):
n = len(lista)
for i in range(n):
trocou = False
for j in range(0, n-i-1):
# A única linha que importa: a comparação.
# Em Python, `>` funciona para strings alfabeticamente.
if lista[j] > lista[j+1]:
lista[j], lista[j+1] = lista[j+1], lista[j]
trocou = True
if not trocou:
break
return lista
# --- Testes da Função com Strings ---
lista_frutas = ["banana", "maçã", "uva", "abacaxi", "laranja"]
lista_nomes = ["Carlos", "Beatriz", "Ana", "Daniel"]
lista_mista = ["Python", "java", "C++", "python"] # 'p' minúsculo vem depois de 'J' maiúsculo
print(f"Lista original de frutas: {lista_frutas}")
print(f"Lista ordenada de frutas: {bubble_sort_strings(lista_frutas.copy())}\n")
print(f"Lista original de nomes: {lista_nomes}")
print(f"Lista ordenada de nomes: {bubble_sort_strings(lista_nomes.copy())}\n")
print(f"Lista original mista: {lista_mista}")
print(f"Lista ordenada mista: {bubble_sort_strings(lista_mista.copy())}\n")
Observação sobre a ordenação mista: A ordenação padrão em Python é sensível a maiúsculas e minúsculas (case-sensitive). Caracteres maiúsculos vêm antes dos minúsculos na tabela ASCII. Para uma ordenação que ignore essa diferença, poderíamos modificar a comparação para `if lista[j].lower() > lista[j+1].lower():`.