# Ordenação e estabilidade

Traçar ordenações, provar a intercalação e distinguir garantias de pior caso e custos esperados.

Página: https://resumos.rgo.pt/cadeiras/aed/ordenacao/

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.

1.  **Metades ordenadas**
    
    `2, 6``1, 5`
    
    1 é menor que 2, por isso sai da metade direita.
2.  **Depois de escrever 1**
    
    `2, 6``5``saída: 1`
    
    2 é menor que 5, depois 5 é menor que 6.
3.  **Junção concluída**
    
    `1``2``5``6`
    
    Três comparações nesta junção; cinco no mergesort completo de quatro valores.

Na junção só comparamos as frentes ainda disponíveis. Copiar o último 6 não exige outra comparação de chaves.

**main.cpp**

```cpp
#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](https://resumos.rgo.pt/cadeiras/aed/listas-pilhas-filas/#separar-e-intercalar-por-liga%C3%A7%C3%B5es) 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

Porque comparar tem um limite inferior

Para `n` chaves distintas, uma ordenação por comparações tem de distinguir `n!` permutações. A árvore de decisões binária precisa de pelo menos `n!` folhas, logo altura pelo menos $\lceil\log_2(n!)\rceil=\Omega(n\log n)$. É um limite de pior caso no modelo de comparação, não um limite para qualquer algoritmo com informação sobre as chaves.

**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:

| Dígito | Entrada | Dígitos lidos | Saída estável |
| --- | --- | --- | --- |
| Unidades | `[170,45,75,90,2]` | `[0,5,5,0,2]` | `[170,90,2,45,75]` |
| Dezenas | `[170,90,2,45,75]` | `[7,9,0,4,7]` | `[2,45,170,75,90]` |
| Centenas | `[2,45,170,75,90]` | `[0,0,1,0,0]` | `[2,45,75,90,170]` |

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.

| Algoritmo | Melhor | Pior | Auxiliar habitual | Estável nesta versão? |
| --- | --- | --- | --- | --- |
| Seleção | $\Theta(n^2)$ | $\Theta(n^2)$ | $O(1)$ | não |
| Inserção | $\Theta(n)$ | $\Theta(n^2)$ | $O(1)$ | sim |
| Bubble com paragem | $\Theta(n)$ | $\Theta(n^2)$ | $O(1)$ | sim |
| Mergesort em vetor | $\Theta(n\log n)$ | $\Theta(n\log n)$ | $O(n)$ | sim |
| Quicksort Lomuto | $\Theta(n\log n)$ | $\Theta(n^2)$ | $O(n)$ na recursão ingénua | não |

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

[Vídeo: Algoritmos de Ordenação 101 (Merge, Quick, Bubble, ...)](https://www.youtube.com/watch?v=HKLRBNuL4DA)

[Abrir no YouTube](https://www.youtube.com/watch?v=HKLRBNuL4DA)

## Exercícios

As justificações e os programas em C++ são de autoavaliação: compara-os com os critérios da solução. Nas questões numéricas, a verificação automática confirma apenas o valor.

Intercalar com contagem exata

Intercala \[1,6,8\] e \[2,3,9\]. Quantas comparações entre os candidatos fazes antes de uma metade acabar?

Pista

Compara apenas as frentes ainda não consumidas.

Mais uma pista

Os candidatos escolhidos são 1, 2, 3, 6 e 8; depois sobra 9.

Solução

Faz cinco comparações: 1/2, 6/2, 6/3, 6/9, 8/9. Copiar o 9 restante não compara candidatos. A saída é \[1,2,3,6,8,9\], porque o prefixo escrito está ordenado e contém os menores elementos da entrada desta junção.

Erros frequentes

Não contes a cópia final como comparação de chaves; não confundas esta junção com todas as chamadas do mergesort.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/aed/ordenacao/#mergesort-e-prova-do-merge)

Separar média e pior caso

Lomuto usa o último pivô e o teste estrito <. Analisa o quicksort de n chaves todas iguais: tamanho das partições, número total de comparações e espaço recursivo ingénuo.

Pista

Nenhum elemento passa no teste estrito.

Mais uma pista

Cada chamada deixa um lado vazio e outro com n-1 elementos.

Solução

O pivô vai para a primeira posição. As comparações somam (n-1)+(n-2)+…+1=n(n-1)/2, portanto Θ(n²). A profundidade recursiva é Θ(n). Um pivô aleatório não corrige este caso se a partição continuar a separar só um igual, porque uma partição em três regiões resolve os iguais num único nível.

Confere a tua resposta:

*   Obtive partições de tamanhos 0 e n-1 em cada chamada.
*   Somei n(n-1)/2 comparações e distingui tempo quadrático de pilha linear.
*   Expliquei por que um pivô aleatório não separa valores iguais.

Erros frequentes

Não atribuas O(log n) à pilha sem provar equilíbrio ou recursar só sobre o lado menor.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/aed/ordenacao/#quicksort-e-parti%C3%A7%C3%A3o)

Ordenar por dois critérios sem perder empates

Tens os registos Rui-15, Ana-12, Rui-12 e Ana-15. Ordenas primeiro pelo nome e depois pela nota crescente. Que garantia precisas para os empates de nota ficarem por nome? Dá a ordem final e um comparador que obtenha essa ordem numa única ordenação.

Pista

A segunda ordenação não deve trocar registos de nota equivalente.

Mais uma pista

Num comparador único, só comparas nomes quando as notas coincidem.

Solução

A segunda ordenação tem de ser estável, porque os empates de nota devem continuar por nome. A ordem final é Ana-12, Rui-12, Ana-15, Rui-15. A primeira ordenação só precisa de colocar os nomes por ordem; a segunda preserva essa ordem dentro de cada nota. Um comparador direto usa `a.nota != b.nota ? a.nota < b.nota : a.nome < b.nome`. `std::sort` pode usar este comparador sem estabilidade porque inclui os dois critérios.

Confere a tua resposta:

*   Obtive Ana-12, Rui-12, Ana-15, Rui-15.
*   Exigi estabilidade na segunda ordenação, por nota.
*   Dei um comparador direto por nota e depois nome, sem usar <=.

Erros frequentes

Ordenar estavelmente por nome no fim faria o nome ser o critério principal.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/aed/ordenacao/#estabilidade-e-compara%C3%A7%C3%A3o-v%C3%A1lida)

Traçar frequências e prefixos

Traça o counting sort em `[(2,A),(1,B),(2,C),(0,D)]` com `k=3`. Porque percorrer da direita conserva a estabilidade?

Pista

Conta primeiro, depois coloca.

Mais uma pista

A última posição livre de cada chave desce a cada escrita.

Solução

Frequências `[1,1,2]`; prefixos acumulados `[1,2,4]`. Percorrendo da direita: D ocupa `1-1=0`; C ocupa `4-1=3`; B ocupa `2-1=1`; A ocupa `3-1=2`, porque escrever C já reduziu a fronteira da chave 2. A saída é `[(0,D),(1,B),(2,A),(2,C)]`. A fica antes de C porque o último registo de cada chave recebe primeiro a última posição livre. Usar estas mesmas fronteiras finais num percurso da esquerda para a direita inverteria os empates; outra versão com posições iniciais pode percorrer da esquerda e ser estável.

Confere a tua resposta:

*   Calculei frequências \[1,1,2\] para o exemplo.
*   Mostrei a escrita da direita para a esquerda.
*   Preservei A antes de C nos empates.

Erros frequentes

Reconstruir só frequências perde os campos dos registos.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/aed/ordenacao/#limite-inferior-e-ordena%C3%A7%C3%A3o-sem-compara%C3%A7%C3%B5es)

Ordenar uma lista com divisões de tamanhos diferentes

Uma lista contém `[5A,1B,5C,3D,2E,5F,4G]`. Tens `separar(resto,k)`, que conserva os primeiros k nós, e `intercalar(outra)`, que junta listas ordenadas e escolhe a esquerda no empate. Escreve os passos de um mergesort, dá as metades da primeira divisão e as metades já ordenadas, depois a saída final. Justifica estabilidade, tempo e espaço auxiliar. As operações alteram ligações, sem copiar os valores ou criar nós.

Solução

O caso base é `n<=1`. Cria uma lista vazia, separa após `floor(n/2)` nós, ordena recursivamente a origem e o resto, e intercala o resto na origem. A primeira divisão cria `[5A,1B,5C]` e `[3D,2E,5F,4G]`; depois de ordenar, são `[1B,5A,5C]` e `[2E,3D,4G,5F]`. A saída é `[1B,2E,3D,4G,5A,5C,5F]`. Escolher a esquerda no empate conserva A e C antes de F; as chamadas também conservam os empates interiores. A divisão linear e a junção linear dão `T(n)=T(floor(n/2))+T(ceil(n/2))+Θ(n)=Θ(n log n)`. A profundidade é logarítmica e cada chamada guarda apenas um número constante de apontadores e tamanhos, por isso o auxiliar é `O(log n)`. A lista temporária fica vazia após a junção e não liberta os nós transferidos.

Confere a tua resposta:

*   Dividi sete nós em três e quatro, sem perder o nó extra.
*   Obtive 1B,2E,3D,4G,5A,5C,5F e conservei a ordem dos três 5.
*   Compus separar, duas chamadas e intercalar, com base n<=1.
*   Justifiquei Θ(n log n) e pilha O(log n), sem vetor auxiliar.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/aed/ordenacao/#mergesort-em-listas-ligadas)