# Pesquisa e ordenação em arrays

Pesquisa sequencial e binária, ordenação por comparação e o confronto quicksort contra mergesort.

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

Ordenar é o problema mais estudado da computação, porque aparece dentro de quase tudo: pesquisar depressa, remover duplicados, juntar conjuntos, preparar dados para outro algoritmo. Esta página fixa a pesquisa em vetores, apresenta as ordenações que tens de saber seguir à mão e explica por que nenhuma ordenação por comparação escapa a $O(n \log n)$.

## Pesquisar: sequencial e binária

A **pesquisa sequencial** percorre o vetor do início ao fim até encontrar o valor ou esgotar as posições: $O(n)$ no pior caso, $O(1)$ de espaço, e funciona em qualquer vetor. A **pesquisa binária** exige o vetor ordenado e compara com o elemento do meio: se o alvo for menor, continua na metade esquerda; se for maior, na direita. Cada comparação corta os candidatos a metade, por isso custa $O(\log n)$, como contaste na página anterior.

Há variantes que deves reconhecer: encontrar a **primeira** ou a **última** ocorrência num vetor com repetidos (quando o meio é igual ao alvo, continua-se para o lado respetivo em vez de parar), e o limite de inserção (a posição onde o valor entraria para manter a ordem). Todas mantêm $O(\log n)$ porque cada passo continua a descartar metade.

## Ordenação por comparação

| Algoritmo | Pior caso | Caso médio | Espaço extra | Estável |
| --- | --- | --- | --- | --- |
| Seleção | $O(n^2)$ | $O(n^2)$ | $O(1)$ | não |
| Inserção | $O(n^2)$ | $O(n^2)$ | $O(1)$ | sim |
| Mergesort | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ | sim |
| Quicksort | $O(n^2)$ | $O(n \log n)$ | $O(\log n)$ | não |

A **ordenação por seleção** repete “escolhe o mínimo do que falta e põe-no na posição”: simples, sempre quadrática, boa quando trocar é caro e comparar é barato. A **ordenação por inserção** insere cada elemento na parte já ordenada: quadrática no geral, mas $O(n)$ num vetor quase ordenado, por isso é a escolha para entradas pequenas. **Estável** significa que elementos iguais mantêm a ordem relativa original, o que interessa quando ordenas por uma chave e há desempates noutra.

O limite fundamental: qualquer algoritmo que só compare pares de elementos precisa de $\Omega(n \log n)$ comparações no pior caso. A intuição é que $n$ elementos têm $n!$ ordens possíveis e cada comparação só distingue dois resultados, por isso são precisas pelo menos $\log_2(n!) \approx n \log n$ comparações para isolar a ordem certa. O mergesort atinge este limite; o quicksort atinge-o em média.

## Mergesort num vetor de 7 elementos

O mergesort divide ao meio, ordena cada metade e **intercala** (merge) as metades ordenadas. Segue o vetor $[5, 2, 7, 1, 6, 3, 4]$:

*   Divide em $[5, 2, 7, 1]$ e $[6, 3, 4]$.
*   A primeira metade divide em $[5, 2]$ e $[7, 1]$, que ordenam para $[2, 5]$ (1 comparação: $5$ contra $2$) e $[1, 7]$ (1 comparação). A intercalação compara $2$ com $1$ (fica $1$), $2$ com $7$ (fica $2$), $5$ com $7$ (fica $5$) e despeja o $7$: $[1, 2, 5, 7]$ com 3 comparações.
*   A segunda metade divide em $[6]$ e $[3, 4]$; esta ordena para $[3, 4]$ (1 comparação) e a intercalação com $[6]$ compara $6$ com $3$ e com $4$: $[3, 4, 6]$ com 2 comparações.
*   A intercalação final de $[1, 2, 5, 7]$ com $[3, 4, 6]$ compara $1$ com $3$, $2$ com $3$, $5$ com $3$, $5$ com $4$, $5$ com $6$ e $7$ com $6$, e despeja o $7$: $[1, 2, 3, 4, 5, 6, 7]$ com 6 comparações.

Total: $1 + 1 + 3 + 1 + 2 + 6 = 14$ comparações. Repara no padrão: cada nível da divisão faz cerca de $n$ comparações e há $\log n$ níveis, daí o $O(n \log n)$. O preço é o vetor auxiliar de tamanho $n$ em cada intercalação.

![Árvore de recursão do mergesort no vetor de 7 elementos, com o número de comparações em cada intercalação: 1, 1 e 1 no primeiro nível de junções, 3 e 2 no segundo, 6 na junção final, total 14.](https://resumos.rgo.pt/cadeiras/aed/pesquisa-ordenacao/figura-1.svg)

Lê a árvore de cima para baixo como divisão e de baixo para cima como junção: os números nas setas de subida são as comparações de cada intercalação, e a soma dá as 14 que contaste à mão.

## Quicksort no mesmo vetor

O quicksort escolhe um **pivô**, **particiona** (menores à esquerda, maiores à direita) e resolve cada lado. Com o esquema de Lomuto e pivô na última posição, a primeira partição de $[5, 2, 7, 1, 6, 3, 4]$ com pivô $4$ faz 6 comparações e produz $[2, 1, 3, 4, 6, 7, 5]$, com o $4$ já na posição final. Resolve $[2, 1, 3]$ (pivô $3$, 2 comparações, fica igual), $[2, 1]$ (pivô $1$, 1 comparação, troca para $[1, 2]$), $[6, 7, 5]$ (pivô $5$, 2 comparações, passa a $[5, 7, 6]$) e $[7, 6]$ (1 comparação, troca para $[6, 7]$). Total: $6 + 2 + 1 + 2 + 1 = 12$ comparações.

```cpp
#include <iostream>
#include <vector>
using namespace std;

int lomuto(vector<int>& v, int lo, int hi) {
    int pivo = v[hi], i = lo;
    for (int j = lo; j < hi; j++)
        if (v[j] < pivo) swap(v[i++], v[j]);
    swap(v[i], v[hi]);
    return i;
}

int main() {
    vector<int> v = {5, 2, 7, 1, 6, 3, 4};
    int p = lomuto(v, 0, 6);
    cout << "pivo na posicao " << p << ": ";
    for (int x : v) cout << x << " ";
    cout << "\n";
}
```

O programa imprime `pivo na posicao 3: 2 1 3 4 6 7 5`: seis comparações, o $4$ na posição final 3, menores à esquerda e maiores à direita, exatamente a primeira partição que seguiste acima.

Neste vetor o quicksort fez menos comparações (12 contra 14) e não usou vetor auxiliar. Mas o seu pior caso é real: com o vetor já ordenado e pivô na ponta, cada partição só isola um elemento e o custo degrada para $O(n^2)$. A defesa é escolher bem o pivô (aleatório, ou mediana de três) e mudar para inserção nas partições pequenas. É por isso que a [STL](https://resumos.rgo.pt/cadeiras/p/templates-stl/) usa uma variante híbrida no `sort`, não o quicksort puro.

O esquema de **Lomuto** usa o último elemento como pivô e um índice que separa os menores. É o mais fácil de escrever sem erros e é o que os testes pedem para seguir à mão. Paga uma troca por cada elemento menor que o pivô, mesmo quando o vetor já está quase arrumado.

O esquema de **Hoare** usa dois índices que caminham um para o outro a partir das pontas e trocam quando se cruzam no sítio errado. Faz menos trocas que o Lomuto (cerca de três vezes menos em média) e é o que as bibliotecas preferem. Em compensação, o pivô não termina necessariamente na posição final, por isso a recursão trata os intervalos com mais cuidado.

Comparações não são tudo

Dois algoritmos com o mesmo $O$ podem diferir por constantes, localidade de cache e número de trocas. O quicksort costuma ganhar ao mergesort na prática porque trabalha no próprio vetor, com acessos sequenciais que a cache adora. A análise assintótica ordena os candidatos; a medição escolhe o vencedor.

## Ordenação linear

Sem comparar pares, o limite $n \log n$ não se aplica. A **counting sort** conta quantas vezes aparece cada valor (quando os valores estão num intervalo pequeno conhecido) e reescreve o vetor: $O(n + k)$ para $k$ valores possíveis. Ordena $[2, 0, 2, 1, 3, 0, 2]$ com valores de 0 a 3: conta um $0$ duas vezes, um $1$ uma vez, um $2$ três vezes e um $3$ uma vez, ou seja a tabela $[2, 1, 3, 1]$; reescreve dois zeros, um um, três dois e um três, e obtém $[0, 0, 1, 2, 2, 2, 3]$. Nenhuma comparação entre elementos, só contagem e escrita. A **radix sort** ordena dígito a dígito com uma ordenação estável auxiliar. O truque é sempre o mesmo: trocar comparações por informação sobre os valores. Quando os valores são arbitrários, volta-se à comparação.

## Ver também

[Vídeo: 15 algoritmos de ordenação em 6 minutos](https://www.youtube.com/watch?v=kPRA0W1kECg)

A miniatura vem do YouTube. O vídeo só carrega quando clicas. [Abrir no YouTube](https://www.youtube.com/watch?v=kPRA0W1kECg)

O vídeo mostra as 15 ordenações a correr lado a lado: vê como o quicksort e o mergesort avançam depressa enquanto a seleção e a inserção ficam para trás. Para brincar com cada comparação, o [Visualgo](https://visualgo.net/en/sorting) anima as trocas passo a passo, e a [documentação do sort da STL](https://en.cppreference.com/w/cpp/algorithm/sort) diz que garantias a implementação real oferece.