Ordenar sem Comparar: Contagem, Radix e a Escolha da Ferramenta

O Artigo 10 terminou com um piso: nenhum algoritmo que só compara elementos ordena $n$ valores com menos de $\lceil {\log }_{2}n!\rceil$ comparações no pior caso. O argumento era de informação. Cada comparação devolve um único bit, sim ou não, e são precisos cerca de $n{\log }_{2}n$ bits para escolher uma entre $n!$ ordens possíveis.

O piso vale para quem só pergunta $a$ é menor que $b$?. Um algoritmo que olha para o valor de uma chave, e não apenas para a sua posição relativa, faz outra pergunta: qual é o valor desta chave?. Quando a chave é um inteiro entre $0$ e $255$, essa pergunta devolve oito bits de uma vez, e a conta do piso deixa de se aplicar. Este artigo trata dos algoritmos que fazem essa pergunta, o counting sort (ordenação por contagem) e o radix sort (ordenação por dígitos), do preço que eles cobram em memória e em cache, e de como escolher entre todas as ferramentas que a série apresentou até aqui. No fim, o exercício resolvido do ranking junta busca, ordenação e contagem em um único problema, e dois problemas mostram que, às vezes, a melhor ordenação é a que não acontece.

As medições foram feitas com o MSVC do Visual Studio 18.10.3, com /std:c++latest /O2, em um Intel Core i7-10750H. Cada tempo é a mediana de cinco execuções depois de uma de aquecimento, e cada execução recebe uma cópia nova dos dados, feita fora do cronômetro. Os programas deste artigo, com as entradas e as saídas esperadas de cada caso de teste, estão em serie-blog/competitiva-11.

1. A informação que a comparação não usa

Vamos começar pelo caso mais favorável. Os valores são inteiros em um intervalo pequeno e conhecido, $[0,k)$, e queremos ordená-los. Em vez de comparar pares, contamos quantas vezes cada valor aparece:

1
2
3
4
5
6

vetor:     4 1 3 1 0 4 1
contagem:  valor 0 aparece 1 vez
           valor 1 aparece 3 vezes
           valor 2 aparece 0 vezes
           valor 3 aparece 1 vez
           valor 4 aparece 2 vezes

Com a tabela de contagens pronta, a ordenação é só reescrever cada valor tantas vezes quantas ele apareceu, do menor para o maior: $0,1,1,1,3,4,4$. Nenhum elemento foi comparado com outro. A posição de cada valor no vetor de contagens já é a sua ordem.

1
2
3
4
5
6
7
8
9
10
11

std::vector<int> contagem_simples(const std::vector<int>& a, int k) {
    std::vector<int> cont(k, 0);
    for (int x : a) ++cont[x];                     // n incrementos

    std::vector<int> saida;
    saida.reserve(a.size());
    for (int valor = 0; valor < k; ++valor)        // k contadores visitados
        for (int c = 0; c < cont[valor]; ++c)
            saida.push_back(valor);
    return saida;
}