Ordenação e estabilidade

Que algoritmo custa o quê

Algoritmo	Quando é bom	Pior caso	Memória extra	Mantém empates
Seleção	Trocas caras e auxiliar $O(1)$	$\Theta(n^2)$	$O(1)$	Não
Inserção	Entrada quase ordenada	$\Theta(n^2)$	$O(1)$	Sim
Bubble com paragem	Entrada ordenada	$\Theta(n^2)$	$O(1)$	Sim
Mergesort	Garantia em todos os casos	$\Theta(n\log n)$	$O(n)$	Sim
Quicksort	Caso médio rápido	$\Theta(n^2)$	Pilha até $O(n)$	Não

• Seleção faz sempre n(n-1)/2 comparações. Em [2A,2B,1] troca o 1 para a frente e inverte os 2.
• Inserção custa $\Theta(n+I)$ com I inversões. Só desloca elementos estritamente maiores.
• Bubble só é linear com paragem quando não há trocas.

Intercalar sem falhar

Divide ao meio, ordena cada metade e junta pelas frentes. Na igualdade, tira da esquerda.

1. Metades
   2, 61, 5
   1 sai da direita, depois 2 da esquerda.
2. Resultado
   1256
   Três comparações; o 6 final copia-se.

Recorrência $T(n)=2T(n/2)+\Theta(n)$ dá $\Theta(n\log n)$. Guarda um auxiliar de n e reutiliza-o. Em lista ligada, separa por ligações e intercala sem copiar valores; a pilha fica $O(\log n)$ e std::list ordena-se com lista.sort().

Partir para o quicksort

Com pivô p=v[r-1] em [l,r):

1. Varre j e mantém menores à esquerda de i.
2. Troca para i quando encontra valor menor que p.
3. Põe o pivô em i e resolve cada lado.

Em [5,2,7,1,4], o pivô 4 termina em [2,1,4,5,7]. Equilíbrio dá $\Theta(n\log n)$; isolar um de cada vez dá $\Theta(n^2)$. Pivô aleatório com chaves distintas dá $O(n\log n)$ esperado. Todas iguais continuam quadráticas em Lomuto; separa três grupos para evitar esse caso. Hoare devolve fronteira, não posição final do pivô.

Quando não basta comparar

• Um comparador válido define uma ordem fraca estrita: comp(x,x) é falso, comp é transitiva e a equivalência induzida também é transitiva. <= e diferenças com overflow falham. Referência: https://eel.is/c++draft/alg.sorting.general .
• sort garante $O(n\log n)$ comparações sem estabilidade. stable_sort conserva empates.
• Comparar tem limite $\Omega(n\log n)$ no pior caso para chaves distintas.
• Counting com chaves em [0,k): conta, prefixa e distribui da direita para a esquerda. Custa $\Theta(n+k)$.
• Radix LSD com d dígitos de base b lê do menos para o mais significativo, sempre com passagem estável. Custa $\Theta(d(n+b))$.

Exemplos completos.