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 C++ 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 C++
A parte à esquerda de i permanece ordenada. O elemento atual é deslocado até encontrar sua posição.
#include <vector>
void insertion_sort(std::vector<int>& valores) {
for (int i = 1; i < static_cast<int>(valores.size()); ++i) {
int chave = valores[i];
int j = i - 1;
while (j >= 0 && valores[j] > chave) {
valores[j + 1] = valores[j];
--j;
}
valores[j + 1] = chave;
}
}Ordenando 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.
#include <string>
struct Produto {
int codigo;
std::string nome;
double preco;
};
bool por_preco(const Produto& a, const Produto& b) {
return a.preco < b.preco;
}
// Uso:
// std::sort(produtos.begin(), produtos.end(), por_preco);sort() ou stable_sort()?
| Recurso | Resultado | Entrada aceita |
|---|---|---|
std::sort | Ordena o intervalo no próprio contêiner. | Não preserva necessariamente a ordem dos equivalentes. |
std::stable_sort | Ordena preservando a ordem relativa dos equivalentes. | Exige memória auxiliar. |
Em C++, escolha std::stable_sort quando objetos com a mesma chave precisarem manter sua ordem relativa original.
std::sort pode combinar técnicas, desde que cumpra as garantias de complexidade do padrão.Sobre o material-base enviado
A aula apresenta Insertion, Selection, Bubble, Merge, Quicksort, Counting Sort e critérios customizados. As complexidades foram revisadas com as definições do NIST e a documentação oficial da linguagem.
- 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.
- cppreference — std::sort: comparadores e garantias de complexidade.