Ordenação bitônica

Aprendi vários algoritmos de ordenação nos cursos da faculdade e na maratona. Entre eles estão o Bubble Sort, o Insertion Sort, o Selection Sort, o Heap Sort, Merge Sort e o Quick Sort. Porém, um no qual eu não tinha ouvido falar é o Bitonic Sort ou Ordenação Bitônica (em tradução livre).

Uma sequência monotonicamente crescente é equivalente a uma sequência não-descrescente, ou seja, seus elementos nunca diminuem, mas podem ficar iguais. A definição de monotonicamente decrescente é análoga. Já uma sequência bitônica, é uma sequência monotonicamente crescente seguida de uma monotonicamente decrescente (ou uma rotação cíclica dessa sequência).

Assim, por exemplo, {1, 2, 2, 3, 7, 6, 4} é uma sequência bitônica, formada pela sequência monotonicamente crescente {1, 2, 2, 3} e pela monotonicamente decrescente {7, 6, 4}. Como {3, 7, 6, 4, 1, 2, 2} é uma rotação cíclica da sequência original, então ela é também bitônica.

 

Figura 1: Exemplo de sequência bitônica

Para facilitar a descrição do algoritmo, vamos supor que o tamanho da sequência é uma pontência de 2.

Bitonic Split

Bitonic Split ou Divisão Bitônica (novamente, uma tradução livre), consiste em dividir a sequência bitônica A de tamanho n em duas novas sequências bitônicas, A1 e A2, de tamanho n/2, com a propriedade adicional de que todos os elementos de A1 são menores ou iguais a quaisquer elementos de A2.

Para isso, criamos a sequência A1 e A2 da seguinte forma:

 

Figura 2: Ilustração da divisão bitônica da Figura 1. A1 está destacado em azul, A2 em verde.

Por exemplo, se o vetor for {1, 5, 6, 9, 8, 7, 3, 0}, teremos A1 = {1, 5, 3, 0} e A2 = {8, 7, 6, 9}. Podemos fazer essa divisão recursivamente, até que restem sequências de apenas um elemento. Essa estratégia está esquematizada na figura a seguir:

Observe que pela propriedade dos elementos da subárvore da esquerda serem sempre menores do que os da direita, no nível das folhas o vetor estará ordenado. Se estivéssemos fazendo essas divisões no próprio vetor teríamos algo do tipo:

Sequência em cada etapa do algoritmo.

Não podemos aplicar esse algoritmo a qualquer subsequência porque usamos a hipótese de que a sequência de entrada era bitônica. Portanto, devemos transformar a sequência de entrada em uma sequência bitônica. Para tanto usaremos um algoritmo baseado no seguinte argumento indutivo: Suponha que sabemos transformar em bitônica cada uma das metades da sequência original. Como, a partir disso, transformar a sequência original em bitônica?

Como cada metade é bitônica, usamos a divisão bitônica para ordená-las. A primeira metade ordenamos em ordem não-decrescente e a segunda metade em ordem não-crescente (é só trocar A1 por A2 no algoritmo). Pronto! A sequência original passou a ser bitônica.

Só resta mostrar a base da indução, que é quando temos 4 elementos, por exemplo {a1, a2, a3, a4}. Nesse caso, quebramos em {a1, a2} e {a3, a4}. Se a1 > a2, trocamos esses elementos de posição. Se a3 < a4, também trocamos eles de posição. Temos então uma sequência bitônica.

Complexidade

Vamos analisar primeiro a complexidade de ordenar uma sequência bitônica com a divisão bitônica recursiva. A cada nível quebramos o array em 2, com um processamento linear para construir A1 e A2. Não há processamento após chamar a recursão. Temos então O(log n) níveis gastando O(n) cada. Portanto, temos O(n log n).

Agora a complexidade do algoritmo para transformar uma sequência qualquer em bitônica. Em cada nó quebramos o array em 2 e após retornar da recursão, é preciso usar o algoritmo anterior para ordenar cada metade, gastando O(n/2 log n/2 + n/2 log n/2) = O(n log n). É fácil ver que em cada nível gastamos O(n log n) e temos O(log n) níveis. Logo, a complexidade total do algoritmo é .

Esse algoritmo poderia ser melhorado, observando que é possível ordenar uma sequência bitônica em O(n) (exercício), o que resultaria na complexidade ótima de ordenação que é O(n log n). Porém, esse algoritmo na forma original é interessante para ser paralelizado. Porém, esse é um assunto que discutiremos em um futuro post.

Código

Eu ia implementar esse algoritmo em python, mas como na Wikipedia já existe essa implementação, decidi fazer uma em C++. Para simplificar, o código supõe que o tamanho do vetor é uma potência de 2. Se não for o caso, basta encontrar o maior elemento do vetor e inserir várias cópias dele no final até completar um tamanho que satisfaça essa propriedade. Depois de ordenado, é só jogar fora os últimos elementos.

#include <stdio.h>
#include <algorithm>

// Ordena sequência bitonica
void BitonicSplit(int *v, int n, bool inc){
    if (n <= 1) return;

    for(int i=0; i<n/2; i++)
        if ((inc && v[i] > v[i+n/2])||
            (!inc && v[i] < v[i+n/2]))
            std::swap(v[i], v[i+n/2]);

    BitonicSplit(v, n/2, inc);
    BitonicSplit(v + n/2, n/2, inc);
}
// Ordena sequência arbitrária
void BitonicSort(int *v, int n, bool inc){
    if (n <= 1) return;

    BitonicSort(v, n/2, inc);        // Ordena cresc.
    BitonicSort(v + n/2, n/2, !inc); // Ordena decresc.
    BitonicSplit(v, n, inc);
}

int main (){

    int v[ ] = {5, 1, 6, 9, 8, 7, 0, 3};
    int n = 8;

    BitonicSort(v, n, true);

    for(int i=0; i<n; i++)
        printf("%d ", v[i]);
    printf("\n");
}

Referência

[1] Parallel Programming with MPI – Peter S. Pacheco
[2] Wikipedia – Bitonic Sorter

Uma resposta a Ordenação bitônica

  1. gabrielsaraiva diz:

    Boa explicação do algoritmo. Bem melhor do que em algumas monografias que encontrei por ai ¬¬.

    Parabéns e muito obrigado por compartilhar seu conhecimento.

%d bloggers like this: