Ordenação de valores e registros
Ordenação: elementos, chaves e critérios
Ordenar significa reorganizar os mesmos elementos segundo uma ordem predeterminada. A sequência final deve estar ordenada e continuar sendo uma permutação da entrada.
O que realmente é comparado?
Quando os elementos são números, o próprio valor pode ser a chave. Quando são objetos, escolhemos um ou mais campos.
- Elemento: o registro completo que será movido.
- Chave: informação usada para decidir a posição.
- Critério: crescente, decrescente ou combinação de campos.
Propriedades importantes
- Estável: preserva a ordem original entre elementos com chaves iguais.
- In-place: usa pouca memória auxiliar além da própria coleção.
- Adaptativo: aproveita alguma ordem já existente na entrada.
- Por comparação: decide a ordem comparando pares de chaves.
Visualização passo a passo
Escolha um algoritmo e acompanhe comparações, trocas e a região que já chegou à posição definitiva ou ordenada.
Algoritmos elementares
A animação do Insertion Sort usa trocas entre vizinhos para deixar o movimento visível. A implementação em Python mais abaixo produz a mesma ordenação usando deslocamentos.
Como cada algoritmo organiza os valores
| Algoritmo | Ideia central | Ponto de atenção |
|---|---|---|
| Insertion Sort | Mantém um prefixo ordenado e insere nele o próximo valor. | É eficiente para entradas pequenas ou quase ordenadas. |
| Selection Sort | Procura o menor valor restante e o coloca na próxima posição. | Faz Θ(n²) comparações mesmo se a entrada já estiver ordenada. |
| Bubble Sort | Compara vizinhos e troca os pares invertidos; os maiores avançam para o fim. | A versão otimizada encerra quando uma passagem não faz trocas. |
| Merge Sort | Divide a sequência, ordena as metades e intercala duas partes já ordenadas. | Em arrays, normalmente precisa de memória auxiliar proporcional a n. |
| Quicksort | Escolhe um pivô e particiona os valores em torno dele antes das chamadas recursivas. | A qualidade das partições determina se o comportamento fica próximo de n log n ou chega a n². |
| Counting Sort | Conta quantas vezes cada chave inteira ocorre e reconstrói a saída. | É apropriado quando o intervalo de chaves k é conhecido e não é excessivamente grande. |
Comparação dos métodos
| Algoritmo | Melhor caso | Médio / típico | Pior caso | Espaço auxiliar típico | Estável? |
|---|---|---|---|---|---|
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Sim |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | Não, na forma usual |
| Bubble Sort otimizado | O(n) | O(n²) | O(n²) | O(1) | Sim |
| Merge Sort em array | Θ(n log n) | Θ(n log n) | Θ(n log n) | O(n) | Sim, na forma usual |
| Quicksort | O(n log n) | O(n log n) | Θ(n²) | O(log n) típico; O(n) no pior caso pela recursão | Não, na forma usual |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(k), ou O(n + k) na versão estável | Pode ser |
k é a quantidade de chaves possíveis ou o tamanho do intervalo considerado. Counting Sort não é um algoritmo geral de comparação.
Insertion Sort em Python
A parte à esquerda de i permanece ordenada. O elemento atual é deslocado até encontrar sua posição.
def insertion_sort(values):
# O prefixo values[:i] já está ordenado no início de cada rodada.
for i in range(1, len(values)):
current = values[i]
j = i - 1
# Abre espaço deslocando para a direita os valores maiores.
while j >= 0 and values[j] > current:
values[j + 1] = values[j]
j -= 1
# Insere o elemento atual na posição livre encontrada.
values[j + 1] = currentOrdenando objetos por vários campos
A função key transforma cada objeto em uma chave. Tuplas são comparadas campo a campo, da esquerda para a direita.
from dataclasses import dataclass
@dataclass
class Produto:
nome: str
categoria: str
preco: float
produtos = [
Produto("Teclado", "periferico", 180.0),
Produto("Mouse", "periferico", 90.0),
Produto("Cabo", "acessorio", 25.0),
]
# sorted cria outra lista; os objetos originais não são alterados.
ordenados = sorted(
produtos,
# categoria crescente, preço decrescente, nome crescente
key=lambda p: (p.categoria, -p.preco, p.nome)
)
for produto in ordenados:
print(produto)sort() ou sorted()?
| Recurso | Resultado | Entrada aceita |
|---|---|---|
lista.sort() | Altera a própria lista e retorna None. | Somente listas. |
sorted(iteravel) | Cria e retorna uma nova lista ordenada. | Qualquer iterável. |
A ordenação do Python é estável. Portanto, objetos com a mesma chave mantêm sua ordem relativa original.
list.sort() e sorted(), aproveitando trechos que já estejam ordenados.Sobre o material-base enviado
O README foi usado para selecionar Insertion, Selection, Bubble, Merge, Quicksort, Counting Sort e critérios customizados. As complexidades desta aula foram revisadas com as definições do NIST e a documentação oficial do Python.
- xTecna — README de Ordenação: roteiro e implementações em várias linguagens.
- NIST — sort: definição formal e critérios para escolher algoritmos.
- NIST — insertion sort: funcionamento e custo quadrático.
- NIST — merge sort: divisão, recursão e Θ(n log n).
- NIST — quicksort: caso típico O(n log n) e pior caso Θ(n²).
- NIST — counting sort: contagem por chave e intervalo limitado.
- Python — Sorting HOWTO: key, reverse, estabilidade e ordenação de objetos.