GilgaLab

Radix Sort

Estive lendo sobre alguns algoritmos de organização e me deparei com o Radix Sort.
Pela definição da NIST:

Definition: A multiple pass distribution sort algorithm that distributes each item to a bucket according to part of the item's key beginning with the least significant part of the key. After each pass, items are collected from the buckets, keeping the items in order, then redistributed according to the next most significant part of the key.

Tradução livre:
Definição: Um algorítmo de organização de vários passos que distribui cada item para um bucket de acordo com parte da chave do item, começando pela parte menos significativa da chave. Após cada passo, os items são recolhidos dos buckets, mantendo os itens em ordem e então redistribuindo de acordo com a próxima parte mais significativa da chave.

Pelas leituras que fiz por aí, um método que me pareceu bastante interessante é aplicar esse algorítmo a cada bit da nossa informação. É claro que isso vai depender da aplicação do algorítmo. No caso que irei trabalhar aqui, estaremos ordenando um vetor com números inteiros positivos.

Vamos supor o seguinte array:

int vetor = {12,22,13,16,31}

Descrevendo cada um desses valores em binário:
12 - 01100
22 - 10110
13 - 01101
16 - 10000
31 - 11111

Pela descrição do algorítmo e pelo método adotado, devemos começar organizando nossa informação pelo bit menos significativo de cada um dos números em nosso array, ou seja, pegamos o bit mais a direita do array e distribuímos os valores em 2 buckets. O bucket onde o bit que estamos olhando é 0 ou ou bucket onde o bit que estamos olhando é 1. Ilustrando isso, temos:

01100 - 12
10110 - 22
01101 - 13
10000 - 16
11111 - 31

Começamos olhando para os bits que estão em negrito. Quando encontrarmos um bit 0, jogamos aquele número para o bucket0. Quando encontrarmos um bit 1, jogamos aquele número para o bucket1. Nossos buckets estão dessa forma agora então:

bucket0 = {12, 22, 16}
bucket1 = {13, 31}

Agora nós devolvemos os valores para dentro do nosso vetor na ordem em que se encontram dentro dos bukets. Primeiro colocamos dentro do vetor todos os valores do bucket0 e depois todos os valores do bucket1. Nosso vetor ficará da seguinte maneira:

vetor = {12, 22, 16, 13, 31}

Agora nós repetimos o processo para o nosso novo vetor, utilizando o próximo bit mais significativo.

01100 - 12
10110 - 22
10000 - 16
01101 - 13
11111 - 31

Nossos buckets ficam:

bucket0 = {12, 16, 13}
bucket1 = {22, 31}

Nosso novo vetor:

vetor = {12, 16, 13, 22, 31}

Repetimos o processo para o próximo bit mais significativo em nosso novo vetor:

01100 - 12
10000 - 16
01101 - 13
11010 - 22
11111 - 31

Nossos buckets ficam:

bucket0 = {16, 22}
bucket1 = {12, 13, 31}

Nosso novo vetor:

vetor = {16, 22, 12, 13, 31}

Repetimos o processo para o próximo bit mais significativo em nosso novo vetor:

10000 - 16
11010 - 22
01100 - 12
01101 - 13
11111 - 31

Nossos buckets ficam:

bucket0 = {16}
bucket1 = {22, 12, 13, 31}

Nosso novo vetor:

vetor = {16,22,12,13,31}

Até então não parece nada arrumado não é mesmo? Mas o útimo passo vai nos revelar algo fantástico! :D

Repetimos o processo para o próximo bit mais significativo em nosso novo vetor:

10000 - 16
11010 - 22
01100 - 12
01101 - 13
11111 - 31

Nossos buckets ficam:

bucket0 = {12, 13}
bucket1 = {16, 22, 31}

Nosso novo (e último) vetor:

vetor = {12, 13, 16, 22, 31}

Aha! Fantástico!

O mais interessante disso tudo é a velocidade desse algorítmo. Em alguns testes que fiz aqui, consegui organizar 20 milhoes de números em apenas 9,3 segundos!
Irei demonstrar a seguir uma versão um pouco mais lenta do algorítmo que desenvolvi porém de mais fácil entendimento. Logo após irei demonstrar a versão do mesmo algorítmo que foi capaz de organizar 100 milhões de números em 15,56 segundos.

O algorítmo 'simples'

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
typedef struct lista {
    int num;
    struct lista *prox;
} lista;
 
void radix_sort(int *, int);
void insere(lista **, int);
int pop(lista **);
void imprime(int *vetor, int tamanho);
 
int main()
{
    int tamanho = 20;
    int vetor[tamanho];
    int i;
 
    srand(time(NULL));
    for(i = 0; i < tamanho; i++) {
        vetor[i] = rand() % tamanho;
    }
 
    imprime(vetor, tamanho);
    printf("\n");
 
    radix_sort(vetor, tamanho);
 
    imprime(vetor, tamanho);
    printf("\n");
 
    return 0;
}
 
void insere(lista **l, int valor)
{
    lista *aux = *l;
 
    if(*l == NULL) {
        *l = (lista *)malloc(sizeof(lista));
        (*l)->num = valor;
        (*l)->prox = NULL;
    } else {
        while(aux->prox != NULL) aux = aux->prox;
        aux->prox = (lista *)malloc(sizeof(lista));
        aux = aux->prox;
        aux->num = valor;
        aux->prox = NULL;
    }
}
 
int pop(lista **l)
{
    int ret;
    lista *aux;
 
    ret = (*l)->num;
    aux = *l;
    *l = (*l)->prox;
    free(aux);
 
    return ret;
}
 
void radix_sort(int *vetor, int tamanho)
{
 
    lista *bucket0 = NULL;
    lista *bucket1 = NULL;
    int i, j;
    int numero_bits;
 
    numero_bits = sizeof(int) * 8;
 
    for(i = 0; i < numero_bits; i++) {
        for(j = 0; j < tamanho; j++) {
            if((((vetor[j] >> i) & 0xf) % 2) == 0)
                insere(&bucket0, vetor[j]);
            else
                insere(&bucket1, vetor[j]);
        }
 
        j = 0;
        while(bucket0 != NULL) {
            vetor[j] = pop(&bucket0);
            j++;
        }
 
 
        while(bucket1 != NULL) {
            vetor[j] = pop(&bucket1);
            j++;
        }
 
    }
 
}
 
void imprime(int *vetor, int tamanho)
{
    int i;
 
    for(i = 0; i < tamanho; i++)
        printf("%d ", vetor[i]);
}

[radix.c]

Essa é a versão 'simples' do algorítmo. Ele utiliza listas para ficar mais simples a inserção e remoção dos registros de nossos buckets. O problema com isso é que conforme aumentamos a quantidade de elementos que queremos organizar o programa fica mais lento. A verdadeira função de ordenação aqui é a função 'radix_sort'. As outras funções fazem parte da implementação da lista.
Vamos então dar uma olhada no programa.

...
    int tamanho = 20;
    int vetor[tamanho];
    int i;
 
    srand(time(NULL));
    for(i = 0; i < tamanho; i++) {
        vetor[i] = rand() % tamanho;
    }
...

Simplesmente declaramos um array com 20 posições e colocamos números randomicos nele que vão de 0 a 19. Esse é o vetor que desejamos ordenar.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

void radix_sort(int *vetor, int tamanho)
{
 
    lista *bucket0 = NULL;
    lista *bucket1 = NULL;
    int i, j;
    int numero_bits;
 
    numero_bits = sizeof(int) * 8;
 
    for(i = 0; i < numero_bits; i++) { // Primeiro loop
        for(j = 0; j < tamanho; j++) { // Segundo loop
            if((((vetor[j] >> i) & 0xf) % 2) == 0)
                insere(&bucket0, vetor[j]);
            else
                insere(&bucket1, vetor[j]);
        }
 
        j = 0;
        while(bucket0 != NULL) {
            vetor[j] = pop(&bucket0);
            j++;
        }
 
 
        while(bucket1 != NULL) {
            vetor[j] = pop(&bucket1);
            j++;
        }
    }
}

Como na explicação sobre o algorítmo, estou usando aqui 2 buckets e o vetor com os dados. O bucket0 recebe os números cujo bit atual sendo verificado é 0, e o bucket 1 recebe os números cujo bit atual sendo verificado é 1.
A variável 'numero_bits' se refere a quantos bits nós iremos verificar para realizar a ordenação. No caso como estamos organizando números inteiros, em teoria (mais tarde discutirei uma maneira melhor de determinar esse número) faz sentido percorremos todos os bits do mesmo. sizeof(int) retorna o número de bytes de um int, se multiplicamos esse valor por 8 temos o número de bits.
O primeiro loop se refere a qual bit estamos olhando e o segundo loop passa por cada elemento para determinar se o bit é 0 ou 1 e jogar o número em seu respectivo bucket.
Acredito que a linha que mais chama a atenção aqui é a linha 13. Vamos a explicação então! Imagine que estou trabalhando com um número de 4 bits apenas que se encontra em vetor[0]. O que essa linha faz é pegar o número inteiro e fazer uma lógica AND com o valor 0xf (eu poderia ter usado 0x1). Suponhamos que o numero no nosso vetor é 4. Então a lógica fica assim:

Deslocar o valor dentro de vetor[0] para a direita em 0 bits (primeira interação).
Em hexa: 0x4 & 0xf
Em binario: 0100 & 1111
Resultado: 0100

Deslocar o valor dentro de vetor[0] para a direita em 1 bit (segunda interação).
Em hexa: 0x2 & 0xf
Em binario: 0010 & 1111
Resultado: 0010

Deslocar o valor dentro de vetor[0] para a direita em 2 bits (terceira interação).
Em hexa: 0x1 & 0xf
Em binario: 0001 & 1111
Resultado: 0001

Deslocar o valor dentro de vetor[0] para a direita em 3 bits (quarta interação).
Em hexa: 0x0 & 0xf
Em binario: 0000 & 1111
Resultado: 0000

O que nos interessa aqui é o bit menos significativo, ou seja, o bit mais a direita. Quando realizamos essa lógica AND, o último bit será 0 ou 1. Se o último bit for 0, temos um número par e então o número deve ser colocado no bucket0. Se o último bit for 1, temos um número ímpar e então o número deve ser colocado no bucket1. O deslocamento que fazemos para a direita é apenas para colocar o bit que desejamos verificar na posição menos significativa do número para que possamos saber se ele deve ir ao bucket0 ou ao bucket1.
A lógica que segue é apenas referente a 'remontar' o vetor com todos os valores que estão no bucket0 e depois todos os valores que estão no bucket1.

O algorítmo um pouco menos simples

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
 
void radix_sort(int *, int, int);
void imprime(int *vetor, int tamanho);
 
int main()
{
    int tamanho = 20;
    int *vetor;
    int i;
    int maior = 0;
    clock_t inicio, fim;
    float periodo;
 
    vetor = (int *)malloc(sizeof(int)*tamanho);
 
    srand(time(NULL));
    for(i = 0; i < tamanho; i++) {
        vetor[i] = (rand() % tamanho)+1;
        if(vetor[i] > maior)
            maior = vetor[i];
    }
 
    imprime(vetor, tamanho);
    printf("\n");
 
    inicio = clock();
    radix_sort(vetor, tamanho, maior);
    fim = clock();
    periodo = (float)(((float)fim-(float)inicio)/CLOCKS_PER_SEC);
 
    printf("Tempo: %.15f\n", periodo);
    imprime(vetor, tamanho);
    printf("\n");
 
    return 0;
}
 
void radix_sort(int *vetor, int tamanho, int maior)
{
 
    int i, j, k, l;
    int numero_bits;
 
    int **temp;
 
    temp = (int **)malloc(sizeof(int *)*2);
    temp[0] = (int *)malloc(sizeof(int)*tamanho);
    temp[1] = (int *)malloc(sizeof(int)*tamanho);
 
    numero_bits = (log(maior)/log(2))+1;
 
    for(i = 0; i < numero_bits; i++) {
        k = 0;
        l = 0;
 
        for(j = 0; j < tamanho; j++) {
            if((((vetor[j] >> i) & 0xf) % 2) == 0) {
                temp[0][k++] = vetor[j];
            } else {
                temp[1][l++] = vetor[j];
            }
        }
 
        temp[0][k] = '0';
        temp[1][l] = '0';
 
        j = 0;
        while(temp[0][j] != '0') {
            vetor[j] = temp[0][j];
            j++;
        }
 
        k=0;
        while(temp[1][k] != '0') {
            vetor[j] = temp[1][k];
            j++;
            k++;
        }
 
    }
}
 
void imprime(int *vetor, int tamanho)
{
    int i;
 
    for(i = 0; i < tamanho; i++)
        printf("%d ", vetor[i]);
}

[radix2.c]

Considerações:

• Essa implementação do algorítmo é apenas para números maiores que 0
• Para compilar com o gcc nçao esqueça de compilar o código com -lm para a biblioteca math

As chamadas feitas para a função clock() antes e depois da chamada de radix_sort() são para que possamos visualizar quanto tempo a execução do algorítmo levou.
A primeira pequena diferença que vemos nesse código é na linha 12, onde agora declaramos nossa variável vetor como um ponteiro para que possamos alocar o espaço necessário para ela em runtime. Isso se faz necessário pois quando executarmos o programa para organizar 20 milhões de registros, não seria possível alocar o espaço necessário na stack.
A segunda pequena diferença que vemos nesse código está na linha 22, onde garantimos que o número sorteado é no mínimo 1.
A terceira pequena diferença é que agora nós já identificamos qual é o maior número do nosso vetor. Isso será útil mais a frente.
As grandes diferenças começam dentro da função radix_sort().
A primeira coisa para se notar é que não usamos mais listas. Inserir e retirar items de um array é mais rápido, logo é isso que usaremos. Nosso bucket agora é a variável temp; temp[0] é o bucket0 e temp[1] é o bucket1.
A segunda coisa a se notar é a forma de como calculamos o numero de bits. Essa linha é de extrema imoprtância pois ela reflete diretamente na perfomance do algorítmo. Suponha que estamos trabalhando em uma plataforma onde a variável int tem 32 bits. Suponha também que o maior número que se encontra em nosso array é o número 230.
Vamos representar então o número 230 em binário:
00000000000000000000000011100110

São 32 bits, apenas 8 bits significativos e 24 bits não significativos. A partir do momento que organizamos os números usando todos os bits significativos é inútil que façamos a verificação para os dígitos não significativos pois eles irão sempre ser colocados no bucket0 e sempre na mesma ordem.
Para entender o cálculo utilizado, precisamos lembrar um pouco da matemática da escola.
2^x = 16
Quanto vale x?
log(base 2) de 16 = x
x = 4

Ou seja, para representarmos 16 números precisamos de 4 bits. Sabemos que o a contagem para os números binários começa em 0, logo com esses 4 bits podemos contar de 0 a 15. Para que o número 16 fosse considerado precisamos adicionar mais 1 bit.
Logo, para representar o número 16 temos: (log(base 2) de 16)+1
Como em C não temos uma forma de calcular log em base 2. nós usamos uma propriedade matemática que diz:

log em base x de y = (log y) / (log x)
Para os que não se lembram log sem menção de base é log em base 10.

Voltando então ao nosso exemplo do número 230. Se calcularmos:
log(base 2) de 230 = x
x = 7,85

Não há possibilidade de termos 0.85 bit. Em C variáveis int se arredondam pra baixo. Logo em nosso caso x vale 7.
2^7 = 128
Não é o suficiente, e matemáticamente falando 7,85 seria arredondado de fato para 8. É por essa razão que somamos 1.
2^8 = 256
Agora sim temos espaço o bastante para o valor 230.

Caso não tenha ficado muito clara a explicação, tente ler novamente e se precisar relembre um pouco de logarítmos. Tenho certeza que ficará mais claro.

O resto da lógica que segue é basicamente o mesmo. Como precisamos de uma forma de identificar quando os números de nosso bucket acabaram, eu optei por dizer que o último número do bucket é 0. É por essa razão que o esse algorítmo só é capaz de organizar números maiores que 0.
Todo o resto é basicamente o mesmo já apresentado antes.

Observações
Se você testou esses algorítmos deve ter percebido que são bastante rápidos. Eu quis determinar o quão rápida essa segunda implementação apresentada é quando comparada ao quicksort e os resultados são impressionantes.

Eis então os algorítmos usados:

Quicksort

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
 
void quicksort(int left, int right, int *v);
void swap(int i, int j, int **v);
 
int main(int argc, char **argv)
{
 
	int MAX;
 
	if(argc < 2) {
		printf("Use: %s numero\n", argv[0]);
		return -1;
	}
 
	MAX= atoi(argv[1]);
 
	int i;
	int *vetor;
    clock_t inicio, fim;
    float periodo;
 
	vetor = (int *)malloc(sizeof(int)*MAX);
 
	srand(time(NULL));
	for(i = 0; i < MAX; i++) {
		vetor[i] = rand() % MAX;
	}
 
	inicio = clock();	
	quicksort(0, MAX-1, vetor);
	fim = clock();
 
    periodo = (float)(((float)fim-(float)inicio)/CLOCKS_PER_SEC);
    printf("Tempo: %.15f\n", periodo);
 
	return 0;
}
 
void quicksort(int left, int right, int *v)
{
	int pivot = v[(left+right)/2];
	int i = left;
	int j = right;
 
	if ( left < right ) {
 
		do {
 
			while (v[i] < pivot) i++;
			while (v[j] > pivot) j--;
 
			if( i <= j ) {
				swap(i, j, &v);
				i++;
				j--;
			}
 
 
		} while( i <= j );
 
		quicksort(left, j, v);
		quicksort(i, right, v);
	}
}
 
void swap(int i, int j, int **v) {
	int aux;
 
	aux = (*v)[j];
	(*v)[j] = (*v)[i];
	(*v)[i] = aux;
 
}

Radixsort

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
 
void radix_sort(int *, int, int);
void imprime(int *vetor, int tamanho);
 
int main(int argc, char **argv)
{
    int tamanho;
    int *vetor;
    int i;
    int maior = 0;
    clock_t inicio, fim;
    float periodo;
 
	if(argc < 2) {
		printf("Use: %s numero\n", argv[0]);
		return -1;
	}
 
	tamanho = atoi(argv[1]);
 
    vetor = (int *)malloc(sizeof(int)*tamanho);
 
    srand(time(NULL));
    for(i = 0; i < tamanho; i++) {
        vetor[i] = (rand() % tamanho)+1;
        if(vetor[i] > maior)
            maior = vetor[i];
    }
 
    //imprime(vetor, tamanho);
    //printf("\n");
 
    inicio = clock();
    radix_sort(vetor, tamanho, maior);
    fim = clock();
    periodo = (float)(((float)fim-(float)inicio)/CLOCKS_PER_SEC);
 
    printf("Tempo: %.15f\n", periodo);
    //imprime(vetor, tamanho);
    //printf("\n");
 
    return 0;
}
 
void radix_sort(int *vetor, int tamanho, int maior)
{
 
    int i, j, k, l;
    int numero_bits;
 
    int **temp;
 
    temp = (int **)malloc(sizeof(int *)*2);
    temp[0] = (int *)malloc(sizeof(int)*tamanho);
    temp[1] = (int *)malloc(sizeof(int)*tamanho);
 
    numero_bits = (log(maior)/log(2))+1;
 
    for(i = 0; i < numero_bits; i++) {
        k = 0;
        l = 0;
 
        for(j = 0; j < tamanho; j++) {
            if((((vetor[j] >> i) & 0xf) % 2) == 0) {
                temp[0][k++] = vetor[j];
            } else {
                temp[1][l++] = vetor[j];
            }
        }
 
        temp[0][k] = '0';
        temp[1][l] = '0';
 
        j = 0;
        while(temp[0][j] != '0') {
            vetor[j] = temp[0][j];
            j++;
        }
 
        k=0;
        while(temp[1][k] != '0') {
            vetor[j] = temp[1][k];
            j++;
            k++;
        }
 
    }
}
 
void imprime(int *vetor, int tamanho)
{
    int i;
 
    for(i = 0; i < tamanho; i++)
        printf("%d ", vetor[i]);
}

[Radixsort]
[Quicksort]

Dados da máquina onde o teste foi feito:

$ uname -a
Linux myhost 2.6.30-ARCH #1 SMP PREEMPT Mon Aug 17 16:06:45 CEST 2009 x86_64 Intel(R) Core(TM)2 Duo CPU E7400 @ 2.80GHz GenuineIntel GNU/Linux
4GB Ram DDR2 800MHz

Eis então uma tabela comparativa do tempo de execução dos algorítmos para quando o maior valor que pode existir dentro do vetor é o próprio tamanho do vetor.
O tempo é dado em segundos

Ao que parece, quicksort vence em todos os testes.
Agora façamos a seguinte alteração nos dois códigos:

No código do quicksort, trocamos

		vetor[i] = rand() % MAX;

por

		vetor[i] = rand() % 1023;

No código do radixsort, trocamos

		vetor[i] = (rand() % tamanho)+1;

por

		vetor[i] = (rand() % 1022)+1;

Eis os novos resultados:

O Radixsort vence todas as comparações!
Logo, dependendo do tipo de dados que se deseja ordenar (caracteres por exemplo), o Radixsort pode ter uma performance superior a do Quicksort.

As implementações do Radixsort aqui apresentadas ainda podem ser otimizadas eu acredito, podendo apresentar uma performance ainda maior!

Referências

http://www.itl.nist.gov/div897/sqg/dads/HTML/radixsort.html
http://www.jimloy.com/computer/radix.htm