Ordenação e Busca¹

Ordenação

A maioria das linguagens de programação modernas implementa uma função de ordenação eficiente. Em C++, tem-se a função sort da biblioteca <algorithm>. Veja alguns exemplos de uso desta função:

int n = 7;
int a[] = {4,2,5,3,5,8,3};
sort(a,a+n); // (1)

vector<int> v = {4,2,5,3,5,8,3};
sort(v.begin(), v.end()); // (2)

vector<pair<int, string>> alunos = {{789, "Paulo"}, {456, "Ana"}, {123, "Paulo"}};
sort(alunos.begin(), alunos.end()); // (3)
for (auto a: alunos)
    cout << a.first << " " << a.second << endl; // (4)

[2, 3, 3, 4, 5, 5, 8]
[2, 3, 3, 4, 5, 5, 8]
Por padrão, um pair sempre é ordenado pelo campo first.
{123, Paulo} {456, Ana} {789, Paulo}

A ordenação padrão é a não-decrescente, mas pode-se obter a ordem inversa da seguinte forma:

vector<pair<int, string>> alunos = {{789, "Paulo"}, {456, "Ana"}, {123, "Paulo"}};
sort(alunos.rbegin(), alunos.rend()); 
for (auto a: alunos) // (1)
    cout << a.first << " " << a.second << endl; 

{789, Paulo} {456, Ana} {123, Paulo}

Para ordernarmos um struct ou class ou outra coleção de objetos (por exemplo, um pair pelo campo second), tem-se duas alternativas: (\(i\)) definir uma função de comparação ou (\(ii\)) fazer a sobrecarga do operador <.

Agora suponha que seja necessário ordenar objetos do tipo Pessoa:

class Pessoa {
public: 
    string nome, sobrenome;
    int idade;
    Pessoa(){ // (1)
        this->nome = "";
        this->sobrenome = "";
        this->idade = 0;
    }
    Pessoa(string _nome, string _sobrenome, int _idade){
        this->nome = _nome;
        this->sobrenome = _sobrenome;
        this->idade = _idade;
    }
    void imprime() {
        cout << "(" << nome << ", " << sobrenome << ", " << idade << ")\n";
    }
};

Construtor padrão usado quando não passamos nenhum argumento para a classe. Sempre faça o construtor padrão. Caso contrário, não será possivel fazer, por exemplo: Pessoa p; //Chama o construtor padrão.

Para ordernarmos um struct ou class ou outra coleção de objetos (por exemplo, um pair pelo campo second), tem-se duas alternativas: (\(i\)) definir uma função de comparação ou (\(ii\)) fazer a sobrecarga do operador <.

Usando uma função de comparação

A primeira alternativa é definir uma função que compara dois objetos e retorna true caso o primeiro seja considerado menor que o segundo e false, caso contrário. Por exemplo,

bool compara(const Pessoa &p1, const Pessoa &p2) { // (1)
        if (p1.nome < p2.nome)
            return true;
        else if (p1.nome == p2.nome) {
            if (p1.sobrenome < p2.sobrenome)
                return true;
            else if (p1.sobrenome == p2.sobrenome)
                return p1.idade > p2.idade;
            else
                return false;
        }
        else
            return false;
}

O const diz ao compilador que os objetos passados para a função não serão alterados internamento. Já o & representa passagem por referência, uma alternativa a passagem por ponteiro. Dessa forma, não passamos uma cópia dos objetos e sim referências (endereços) dos mesmos, o que torna o código mais eficiente. Por quê?

Com a função de comparação definida, basta passá-la como argumento na função sort:

int main() {
    Pessoa p1("Paulo", "Roberto", 35);
    Pessoa p2("Paulo", "Alberto", 30);
    Pessoa p3("Paulo", "Roberto", 40);

    vector<Pessoa> lista;
    lista.push_back(p1); // (1)
    lista.push_back(p2);
    lista.push_back(p3);
    for (auto p: lista)
        p.imprime();
    cout << "\n";
    sort(lista.begin(), lista.end(), compara); // (2) 
    for (auto p : lista)
        p.imprime();

    return 0;
}

Inclui o elemento no fim do vector. Leia mais sobre vector aqui.
Usa a função compara para fazer a ordenação.

Também é possivel usar uma função lambda como função de comparação. Por exemplo, para ordenar um pair pelo campo second (ou usando-o como critério de desempate), pode-se fazer:

bool compara(const pair<int, int> &p1, const pair<int, int> &p2) {
    if (p1.first < p2.first)
        return true;
    else if (p1.first == p2.first)
        return p1.second < p2.second;
    else
        return false;
}

int main() {
    vector<pair<int, int>> pontos = {{0, 2}, {0, 1}, {0, 0}, {0, -5}, {1, 2}, {-1, 10}};

    sort(pontos.begin(), pontos.end(), compara); // (1)
    for (auto a: pontos) // (2)
        cout << "(" << a.first << ", " << a.second << ") ";

    sort(pontos.begin(), pontos.end(), [](const pair<int, int> &p1, const pair<int, int> &p2) { // (3)
        if (p1.first < p2.first)
            return true;
        else if (p1.first == p2.first)
            return p1.second < p2.second;
        else
            return false;
    }); 
    for (auto a: pontos) 
        cout << "(" << a.first << ", " << a.second << ") ";

    return 0;
}

Usando a função compara
(-1, 10) (0, -5) (0, 0) (0, 1) (0, 2) (1, 2)
Usando função lambda

Fazando a sobrecarga do operador `<`

Ao invés de ser difinidas funções de comparações, pode-se fazer a sobrecarga do operador < (operator<). Isso é comum ao se usar class ou struct. Veja como ficaria ao ser considerado a classe Pessoa:

class Pessoa {
public: 
    string nome, sobrenome;
    int idade;
    Pessoa(){ 
        this->nome = "";
        this->sobrenome = "";
        this->idade = 0;
    }
    Pessoa(string _nome, string _sobrenome, int _idade){
        this->nome = _nome;
        this->sobrenome = _sobrenome;
        this->idade = _idade;
    }
    bool operator<(const Pessoa &p){ // (1)
        if (nome < p.nome)
            return true;
        else if (nome == p.nome) {
            if (sobrenome < p.sobrenome)
                return true;
            else if (sobrenome == p.sobrenome)
                return idade > p.idade;
            else
                return false;
        }
        else
            return false;

    }
    void imprime() {
        cout << "(" << nome << ", " << sobrenome << ", " << idade << ")\n";
    }
};

int main() {
    Pessoa p1("Paulo", "Roberto", 35);
    Pessoa p2("Paulo", "Alberto", 30);
    Pessoa p3("Paulo", "Roberto", 40);

    vector<Pessoa> lista;
    lista.push_back(p1); 
    lista.push_back(p2);
    lista.push_back(p3);
    for (auto p: lista)
        p.imprime();
    cout << "\n";
    sort(lista.begin(), lista.end()); // (2) 
    for (auto p : lista)
        p.imprime();

    return 0;
}

Sobrecarga/definição do operador < para a classe Pessoa. Dessa forma, é possivel fazer a comparação p1 < p2, considerando que p1 e p2 são objetos do tipo Pessoa.
Usa o operador < para fazer a ordenação.

Complemente sua leitura e seu conhecimento

Busca

Busca sequencial

A forma mais intuitiva para procurar um elemento em um array é usar um loop que percorre todos os elementos do array e parando assim que o elemento buscado é encontrado. No pior caso, é necessário percorrer todos os elementos, logo a complexidade será \(O(n)\). O código abaixo verifica se x está no array:

for (int i = 0; i < n; i++) {
    if (array[i] == x) {
        // x encontrado na posição i
    }
}

Em C++, pode-se usar a função search.

Busca binária

Se os elementos do array estiverem ordenados, pode-se usar uma estratégia diferente e mais eficiente para realizar a busca: verifique se o elemento do meio do array é o elementos buscado, se for, a busca termina. Caso não seja, verique se o elemento do meio é menor que elemento buscaso, se for, repita o processo considerando apenas a segunda metade do array. Senão, considere a primeira metade do array. Assim, a cada passo da busca, o tamanho do array é reduzido a metade, logo, a complexidade do algoritmo é \(O(\log n)\).

int buscaBinaria(vector<int> v, int x) {
    int ini = 0, fim = v.size()-1;
    while (ini <= fim) {
        int meio = ini + (fim - ini) / 2; // (1)
        if (v[meio] == x) return meio;
        else if (v[meio] < x) ini = meio + 1;
        else fim = meio - 1;
    }
    return -1; // (2)
}

Evite usar meio = (ini + fim) / 2;, já que ini + fim pode gerar integer overflow.
x não está no vetor v.

Em C++, pode-se usar a função std::binary_search. As funções abaixo também são úteis e baseadas na busca binária:

std::lower_bound: retorna um ponteiro para o primeiro elemento do array cujo valor é pelo menos x;
std::upper_bound: retorna um ponteiro para o primeiro elemento do array cujo valor é maior que x;

As funções assumem que o array está ordenado. Se o valor procurado não for encontrado, é retornado um ponteiro para o elemento após o último elemento do array. Por exemplo, o código a seguir verifica se o array contém um elemento com valor x:

vector<int> v = {1, 2, 3, 5, 8, 10, 20};
int x = 10;
auto k = lower_bound(v.begin(), v.end(), x);
if (k != v.end() && *k == x) {
    // x encontrado no indice k
    cout << "Valor encontrado na posição: " << k - v.begin() << endl; // (1)
}

Pode-se usar a função std::distance ao invés de k - v.begin(), ou seja, distance(v.begin(), k).

Complemente sua leitura e seu conhecimento:

Busca binária em funções monotônicas²

Considere uma função booleana \(f(x)\) e se deseja encontrar o valor máximo (ou mínimo) de \(x\) tal que \(f(x)\) seja true. Da mesma forma que a busca binária só funciona se o array estiver ordenado, só é possivel aplicar a busca binária em uma função monótona, ou seja, é sempre não-decrescente ou sempre não-crescente.

Seja check(x) uma função que verifica uma propriedade de x. Se para todo x, check(x) = true implica check(x+1) = true, ou para todo x, check(x) = false implica check(x+1) = false, então a função check é monótona.

Suponha a função check abaixo que verifica se um elemento é maior ou igual a x.. Se x = 11 e o vetor v = [1,2,3,5, 8, 11, 12, 14, 16], então teremos o seguinte vetor de saída ao aplicarmos check em v: [0,0,0,0,0,1,1,1,1,1].

bool check(int val) {
    return val >= x;
}

Dessa forma, a função check para essa situação é monótona e isso é relevante porque se um valor do vetor satisfizer a condição, todos os valores a direita também vão satisfazê-la, e de forma análoga, todos os valores a esquerda de um índice que não satisfaz a condição, também não vão satisfazer, e é isso que nos permite aplicar busca binária. Além disso, a função check só se torna monótona nesse exemplo quando o vetor está ordenado, por isso a busca binária só é feita em vetores ordenados.

Como encontrar o menor valor que torna check verdadeiro? R. inicia-se o processo "chutanto" um intervalo onde a resposta com certeza estará. Para cada intevalo, checa-se o meio e, dependendo da resposta, descarta-se os elementos a direita ou a esquerda, mas sempre divide-se o tamanho do intervalo por 2, até que o intervalo tenha tamanho 1. Veja uma solução:

int l = a;// sei que a resposta não é menos que a
int r = b;// sei que a resposta não é mais que b

while(r > l+1){// repita enquanto o intervalo tiver tamanho > 2
    int mid = l + (r - l)/2;
    if(check(mid)){ // mid é válido
        r = mid; // como queremos minimizar a resposta, e mid é uma resposta válida
                 //descartamos tudo a direita de mid (mas não mid)
    }
    else{
        l = mid + 1; // Se mid não é válido, descartamos ele e tudo abaixo.
    }
}
// Ao final desse laço, a resposta pode estar em l ou r.
// Queremos minimizar a resposta, então se l for válido,
// ficaremos com l, e caso contrário,  com r
int ans = r;
if(check(l)) ans = l;

Exemplo: Encontrar o maior valor de \(x \in [0, 10]\) tal que \(x^2 \leq 30\).

bool check(int val) {
    return val*val <= 30;
}
int lastTrue(int ini, int fim) {
    ini--; // Se nenhum valor no intervalor for true, retorna ini - 1
    while (ini < fim) {
        int m = ini + (fim - ini) / 2;
        if (check(m)) ini = m; // (1)
        else fim = m - 1; // (2)
    }
    return ini;
}

Se check(m) é true, então todos os números menores que m também serão true.
Se check(m) é false, então todos os números maiores que m também serão false.

Two-Pointers

Na técnica chamada Two-Pointers dois "aponstadores" caminham pelo vetor. Normalmente, esses apontadores são ``colocados'' nas extremidades opostas do vetor e caminham um em direção ao outro, como mostra a figura abaixo.

Você consegue pensar em como usar esse técnica para resolver o problema de inverter os elementos de um vetor sem usar um vetor auxiliar? A ideia é simples: coloque cada apontador (digamos i e j) em uma extremidade do vetor, ou seja, i = 0 e j = n - 1, e, a cada iteração, troque os elementos que estão nas posições i e j (ou seja, v[i] <-> v[j]). Após a troca, incremente o apontador i e decremente o apontador j. Repita esse processo enquanto i < j. A figura abaixo ilustra parte desse processo.

O código abaixo ilustra essa estratégia (note a simplicidade):

void inverte(vector<int> &v) { // (1)
    int i = 0;
    int j = v.size() - 1;
    while ( i < j ) {
        swap(v[i], v[j]); // (2)
        i++;
        j--;
    }
}

A std::reverse também pode ser usada com o mesmo objetivo. O intuito é mostrar com a técnica Two-Pointers funciona.
std::swap