Ordenação e estabilidade

Ordenar [6,2,5,1] produz [1,2,5,6]. A saída respeita a comparação crescente e conserva os mesmos elementos, incluindo repetidos.

Se só procuras o máximo, um percurso chega. Se vais fazer muitas pesquisas binárias, pagar a ordenação pode compensar. A decisão depende do uso posterior, não apenas do tamanho.

A regra que decide qual de dois elementos vem primeiro chama-se comparador. Para registos com a mesma chave, importa também saber se a ordenação conserva a sua ordem inicial.

Ordenações elementares

Uma ordenação é estável quando conserva a ordem relativa de elementos com chaves equivalentes. A seleção pode trocar elementos distantes e inverter empates. A inserção e a bubble conservam-nos quando deslocam ou trocam apenas elementos estritamente fora de ordem.

Na seleção, antes de tratares a posição i, o prefixo [0,i) já contém os i menores elementos nas posições finais. Procura o mínimo no sufixo e troca-o com v[i].

Faz $n(n-1)/2$ comparações em qualquer entrada, ou seja, $\Theta(n^2)$. Usa apenas $O(n)$ trocas. Não é estável: em [2A,2B,1], a primeira troca produz [1,2B,2A].

Na inserção, o prefixo [0,i) está ordenado e contém os elementos originais desse prefixo. Guarda v[i], desloca para a direita os elementos estritamente maiores e insere o valor no espaço aberto.

[4,2,3] passa por [2,4,3] e [2,3,4]. Deslocar apenas os estritamente maiores preserva a ordem dos empates. O número de deslocações é o número de inversões, ou seja, pares fora de ordem. O custo é $\Theta(n+I)$, com I inversões. Uma entrada ordenada dá linear; uma inversa dá quadrático.

Na bubble sort, compara vizinhos e troca quando estão invertidos. Uma passagem leva o máximo do intervalo para o fim. Sem uma condição de paragem, continua quadrática mesmo se a entrada já estiver ordenada. Com um indicador de ausência de trocas, o melhor caso é linear. Trocar só elementos estritamente fora de ordem torna-a estável.

Mergesort e prova do merge

Divide [l,r) em [l,m) e [m,r), ordena cada metade e intercala-as. Durante a intercalação, o prefixo auxiliar já escrito contém os menores elementos da entrada da junção, por ordem; i e j apontam para o primeiro elemento não consumido de cada metade. O menor dos dois candidatos é o menor de todos os elementos restantes, porque cada metade está ordenada. Escrevê-lo preserva o invariante. Quando uma metade acaba, copia a outra.

Traça [6,2,5,1]: as metades ordenam para [2,6] e [1,5]. O merge escolhe 1, depois 2, depois 5 e copia 6. Faz três comparações nesta junção; as duas junções inferiores fizeram uma cada, dando cinco no total.

#include <algorithm>
#include <iostream>
#include <vector>
void mergeSort(std::vector<int>& a, std::vector<int>& t,
               std::size_t l, std::size_t r) {
    if (r - l < 2) return;
    const auto m = l + (r - l) / 2;
    mergeSort(a, t, l, m);
    mergeSort(a, t, m, r);
    auto i = l, j = m, k = l;
    while (i < m && j < r)
        t[k++] = a[j] < a[i] ? a[j++] : a[i++];
    while (i < m) t[k++] = a[i++];
    while (j < r) t[k++] = a[j++];
    for (k = l; k < r; ++k) a[k] = t[k];
}
int main() {
    std::vector<int> a{5, 2, 7, 1, 6, 3, 4, 2}, t(a.size());
    auto esperado = a;
    std::sort(esperado.begin(), esperado.end());
    mergeSort(a, t, 0, a.size());
    for (std::size_t i = 0; i < a.size(); ++i)
        std::cout << (i ? " " : "") << a[i];
    std::cout << '\n';
    std::cout << "igual a sort: " << (a == esperado) << '\n';
}

Na igualdade, o programa escolhe o elemento da esquerda e preserva a estabilidade. A divisão termina quando o intervalo tem menos de dois elementos, incluindo o vetor vazio. O vetor auxiliar é criado uma vez e reutilizado. A referência com std::sort parte de uma cópia da entrada original e verifica ordem e preservação dos valores.

A recorrência é $T(n)=2T(n/2)+\Theta(n)$, logo $\Theta(n\log n)$ em melhor, médio e pior caso nesta implementação. O auxiliar ocupa $\Theta(n)$ e a pilha $O(\log n)$. Criar um novo vetor por chamada aumenta alocações, mas não obriga a manter o trabalho de todos os níveis em memória ao mesmo tempo.

Mergesort em listas ligadas

Numa lista simplesmente ligada não tens acesso direto ao meio, mas podes encontrá-lo por um percurso. Separar e intercalar por ligações permite ordenar sem copiar valores nem criar nós auxiliares:

1. Com zero ou um nó, termina.
2. Separa os primeiros n/2 nós dos restantes numa lista inicialmente vazia.
3. Ordena recursivamente as duas listas.
4. Intercala-as, escolhendo a esquerda no empate e esvaziando a lista temporária.

Em [4A,1B,4C,2D,4E], a primeira separação cria [4A,1B] e [4C,2D,4E]. As chamadas devolvem [1B,4A] e [2D,4C,4E]; a junção dá [1B,2D,4A,4C,4E]. Todos os nós da metade esquerda precediam os da direita na entrada. Por isso escolher a esquerda numa igualdade, juntamente com a estabilidade de cada chamada, conserva 4A,4C,4E nessa ordem.

Separar custa $\Theta(n)$ neste nível e intercalar custa $O(n)$; a recorrência é $T(n)=T(\lfloor n/2\rfloor)+T(\lceil n/2\rceil)+\Theta(n)$, dando $\Theta(n\log n)$. Há $O(\log n)$ chamadas suspensas, com um número constante de apontadores por chamada. O auxiliar é, portanto, $O(\log n)$, sem o vetor de $O(n)$ usado na versão anterior. A lista temporária é um objeto com cabeça e tamanho, não uma cópia de metade dos nós.

std::sort exige iteradores de acesso direto e não serve para std::list. O método lista.sort() permite ordenar uma std::list com estabilidade e $O(n\log n)$ comparações. Ordenar uma lista com seleção por percursos repetidos, movendo o máximo do prefixo para o fim, também é possível, mas soma $n+(n-1)+\cdots+2$ visitas e custa $\Theta(n^2)$.

Quicksort e partição

No esquema de Lomuto, para um intervalo não vazio [l,r), escolhe p=v[r-1]. Percorre j=l..r-2 e mantém [l,i) com valores menores que p e [i,j) com valores maiores ou iguais. Se v[j]<p, troca com v[i] e avança i. No fim, troca o pivô com v[i]. O pivô fica na posição final; resolve [l,i) e [i+1,r).

Em [5,2,7,1,4], o pivô é 4. Depois de processares 5, 2, 7 e 1, o vetor fica [2,1,7,5,4]; a troca final produz [2,1,4,5,7]. Foram quatro comparações com o pivô. A partição não ordena cada lado.

Se as divisões forem equilibradas, o custo é $\Theta(n\log n)$. Se cada pivô isolar um único elemento, $T(n)=T(n-1)+\Theta(n)=\Theta(n^2)$. O último elemento como pivô provoca esse caso numa sequência crescente; com a comparação estrita, todos os valores iguais também o provocam.

Com chaves distintas, escolher o pivô uniformemente ao acaso dá custo esperado $O(n\log n)$, mas não elimina o pior caso. Com Lomuto e todas as chaves iguais, a aleatoriedade não muda as partições: o custo continua quadrático. Uma partição em três regiões, menores, iguais e maiores, evita repetir trabalho nos empates. A pilha do quicksort recursivo ingénuo pode ocupar $\Theta(n)$ no pior caso. Recursar só sobre a região menor e iterar sobre a maior limita a pilha a $O(\log n)$, mesmo quando o tempo é quadrático.

O esquema de Hoare aproxima dois índices e troca pares fora da região pretendida. A fronteira devolvida não tem de ser a posição final do pivô. Não combines os intervalos recursivos de Lomuto com a fronteira de Hoare.

Estabilidade e comparação válida

Ao ordenares registos primeiro pelo nome e depois pela nota com uma ordenação estável, os empates de nota continuam por nome. Podes obter a mesma ordem final com um comparador que inclua ambos os critérios.

O comparador de C++ deve definir uma ordem fraca estrita: comp(x,x) é falso; a relação é transitiva; a equivalência definida por nem comp(a,b) nem comp(b,a) também é transitiva. <= não serve. Subtrair duas chaves para decidir a ordem pode causar overflow, por isso compara-as diretamente. Não uses uma tolerância de ponto flutuante que torne a equivalência não transitiva.

std::sort garante $O(n\log n)$ comparações no pior caso em C++17 e não garante estabilidade. O padrão não exige uma implementação concreta. std::stable_sort preserva os empates; com memória auxiliar suficiente faz $O(n\log n)$ comparações, e sem essa memória pode usar $O(n\log^2 n)$. O custo de copiar ou comparar os registos pode acrescentar outro fator.

Limite inferior e ordenação sem comparações

Counting sort usa chaves inteiras em [0,k). Conta frequências, calcula prefixos das contagens e coloca cada elemento na sua posição. Para preservares empates, percorre a entrada da direita para a esquerda e reduz a posição final disponível da respetiva chave. Para [(2,A),(1,B),(2,C),(0,D)], a saída é [(0,D),(1,B),(2,A),(2,C)]. Com k=3, as frequências são [1,1,2]. As somas acumuladas [1,2,4] indicam as fronteiras depois de cada grupo de chaves. Subtrair um à fronteira dá a última posição livre dessa chave. Depois de escrever um registo, reduz a fronteira. Percorre da direita para a esquerda: (0,D) ocupa 0; (2,C) ocupa 3; (1,B) ocupa 1; (2,A) ocupa 2. Escrever da direita preserva A antes de C. Reconstruir só frequências ordena números, mas perde os outros campos dos registos.

O tempo é $\Theta(n+k)$ e o espaço auxiliar da versão estável é $\Theta(n+k)$. Um intervalo enorme de chaves pode tornar esta escolha pior que comparar. Radix sort por dígitos do menos significativo para o mais significativo exige uma ordenação estável em cada passagem; isso conserva a ordem dos dígitos já processados. Com [170,45,75,90,2] e base 10, cada passagem lê a sequência produzida pela anterior:

Nas dezenas, 170 e 75 têm o mesmo dígito 7. A estabilidade conserva 170 antes de 75, mantendo a ordem das unidades, 0 antes de 5. Nas centenas, os valores com dígito 0 conservam a ordem dos dois dígitos inferiores.

Depois de d passagens, a ordem dos d dígitos processados está correta; o custo é $\Theta(d(n+b))$ com base b. Chaves negativas e comprimentos diferentes exigem uma representação e uma política explícitas.

Para uma visão geral de merge, quicksort e bubble sort, podes consultar Rodrigo Dias:

Algoritmos de Ordenação 101 (Merge, Quick, Bubble, ...)Carregar vídeo do YouTube

Abrir no YouTube