§1  RADIX SORT  INTRODUÇÃO 1

1. Introdução. Esta é uma adaptação de um código escrito por Knuth [D. E. Knuth, The Stanford GraphBase: a Platform for Combinatorial Computing, (New York: ACM Press, 1993), viii+576pp. Copublicado pela Addison–Wesley Publishing Company, ISBN 0-201-54275-7; Veja o módulo GB SORT daquele pacote]. De fato, muita coisa é só tradução (e omissão de coisas além do escopo ou irrelevantes para nós). #include /∗ o ponteiro (Λ) é definido aqui ∗/

⟨ Declarations 2 ⟩

⟨ The gb linksort routine 5 ⟩

2. A rotina de maior interesse aqui é uma rotina chamada gb linksort ( ) que ordena (reorganiza) os elementos de uma lista ligada em ordem decrescente de seus campos key , que é um long. Assumimos que estes campos key contém inteiros não negativos menores que 2^{31}.

Após a ordenação, os elementos da lista original estarão organizados em 128 listas ligadas: gb sorted [127], gb sorted [126], …, gb sorted [0]. Para examinar os elementos em ordem decrescente de suas chaves, podemos varrer os elementos com rotinas como a seguinte:

{

int j; node ∗ p; for (j = 127; j ≥ 0; j^{−})

for (p = gb sorted [j]; p; p = p link )

look at (p);

}

Faremos isto abaixo para imprimir as chaves dos elementos em ordem decrescente. Naturalmente, não seria difícil reverter a ordem das listas.

Todos os elementos cujas chaves estão no intervalo j2^{24} ≤ key < (j + 1)2^{24} vão aparecer na lista gb sorted [j]. Portanto, o resultado pode ser encontrado inteiramente contido na lista gb sorted [0] se todas as chaves são estritamente menores que 2^{24}. ⟨ Declarations 2 ⟩ ≡

typedef struct node struct { long key ; /∗ quantidade numérica, que deve ser não-negativa ∗/ struct node struct ∗link ; /∗ apontador para o próximo elemento da lista ∗/

} node; /∗ estes serão os elementos da lista a ser processada ∗/

See also section 4. This code is used in section 1.

3. Aqui está o header file que os usuários deste módulo devem usar. ⟨ 3 ⟩ ≡

typedef struct node struct { long key ; /∗ quantidade numérica, que deve ser não-negativa ∗/ struct node struct ∗link ; /∗ apontador para o próximo elemento da lista ∗/

} node; /∗ estes serão os elementos da lista a ser processada ∗/

extern void gb linksort ( ); /∗ procedure to sort a linked list ∗/

extern node ∗gb sorted [ ]; /∗ the results of gb linksort ∗/

4. Faremos 4 passadas do radix sort, com radix (base) 256. (Veja, por exemplo, Algoritmo 5.2.5R in Sorting and Searching, de Knuth). Nós movemos os elementos da lista entre dois vetores de listas: os vetores gb sorted (que conterá o resultado final) e alt sorted (que conterá resultados intermediários). ⟨ Declarations 2 ⟩ +≡

node ∗gb sorted [256]; /∗ vetor de listas, para as passadas pares ∗/

2  INTRODUÇÃO  RADIX SORT §5

static node ∗alt sorted [256]; /∗ vetor auxiliar, para as passadas ímpares ∗/ 5. Aqui estão as 4 passadas. ⟨ The gb linksort routine 5 ⟩ ≡

void gb linksort (l)

node ∗l; { register long k; /∗ índice para a lista-destino ∗/

register node ∗∗pp; /∗ ponto corrente na lista de ponteiros ∗/ register node ∗p, ∗q; /∗ ponteiros para manipulação de listas ∗/ ⟨ Partition the given list into 256 sublists alt sorted by low-order byte 6 ⟩; ⟨ Partition the alt sorted lists into gb sorted by second-lowest byte 7 ⟩; ⟨ Partition the gb sorted lists into alt sorted by second-highest byte 8 ⟩; ⟨ Partition the alt sorted lists into gb sorted by high-order byte 9 ⟩;

}

This code is used in section 1.

6. ⟨ Partition the given list into 256 sublists alt sorted by low-order byte 6 ⟩ ≡

for (pp = alt sorted + 255; pp ≥ alt sorted ; pp^{−}) ∗pp = Λ;

/∗ inicializamos todas as listas-destino ∗/ for (p = l; p; p = q) {

k = p key &^{#}ff; /∗ extraímos os oito bits menos significantivos ∗/ q = p link ; p link = alt sorted [k]; alt sorted [k] = p;

}

This code is used in section 5.

7. Agora vamos ler as listas de alt sorted de 0 a 255, e vamos classificar os elementos de acordo com o segundo byte menos significativo. ⟨ Partition the alt sorted lists into gb sorted by second-lowest byte 7 ⟩ ≡

for (pp = gb sorted + 255; pp ≥ gb sorted ; pp^{−}) ∗pp = Λ;

/∗ inicializamos todas as listas-destino ∗/ for (pp = alt sorted ; pp < alt sorted + 256; pp^{++})

for (p = ∗pp; p; p = q) { k = (p key ≫ 8) &^{#}ff; /∗ extraímos os proximos oito bits ∗/ q = p link ; p link = gb sorted [k]; gb sorted [k] = p;

}

This code is used in section 5.

8. Agora lemos as listas de 255 a 0, para obter a ordem correta no final. (Cada passada reverte a ordem dos elementos da lista; é meio peculiar mas funciona assim!) ⟨ Partition the gb sorted lists into alt sorted by second-highest byte 8 ⟩ ≡

for (pp = alt sorted + 255; pp ≥ alt sorted ; pp^{−}) ∗pp = Λ;

/∗ inicializamos todas as listas-destino ∗/ for (pp = gb sorted + 255; pp ≥ gb sorted ; pp^{−})

for (p = ∗pp; p; p = q) { k = (p key ≫ 16) &^{#}ff; /∗ extraímos os proximos oito bits ∗/ q = p link ; p link = alt sorted [k]; alt sorted [k] = p;

}

This code is used in section 5.

9. Os 8 bits mais significativos corresponderão a números entre 0 e 127, porque assumimos que os campos key são inteiros menores que 2^{31}. (Uma rotina similar funcionaria para int, ou unsigned long, mas aí o funcionamento da rotina dependeria da representação binária dos números na máquina, o que afetaria a portabilidade deste programa.) ⟨ Partition the alt sorted lists into gb sorted by high-order byte 9 ⟩ ≡

for (pp = gb sorted + 255; pp ≥ gb sorted ; pp^{−}) ∗pp = Λ;

/∗ inicializamos todas as listas-destino ∗/ for (pp = alt sorted ; pp < alt sorted + 256; pp^{++})

for (p = ∗pp; p; p = q) { k = (p key ≫ 24) &^{#}ff; /∗ extraímos os oito bits mais significativos ∗/ q = p link ; p link = gb sorted [k]; gb sorted [k] = p;

}

This code is used in section 5.

10. Aqui está um programa muito simples para ilustrar o uso da rotina gb linksort ( ) implementada acima. Supomos que o usuário executa este programa com um parâmetro N; este programa então gera N inteiros aleatórios usando a função rand ( ) e os coloca em uma lista ligada. Esta lista ligada é então fornecida como argumento em uma chamada de gb linksort ( ). A saída do programa é a lista de números gerados em ordem decrescente. ⟨ 10 ⟩ ≡ #include #include #include

int main(int argc, char ∗argv [ ])

{ long j, k, N = atol (argv [1]); node ∗p, ∗q; p = Λ; while (N^{−} > 0) {

q = (node ∗) malloc(sizeof (node));

q key = rand ( ); q link = p; p = q;

}

gb linksort (p);

for (j = 127; j ≥ 0; j^{−}) {

for (p = gb sorted [j]; p; p = p link ) printf ( , p key ); } return 0;

}

§11  RADIX SORT  ÍNDICE 5

11. Índice. Aqui estão os identificadores usados neste programa, com seus respectivos locais de definição e uso.

alt sorted : \underline{4}, 6, 7, 8, 9. argc: \underline{10}. argv : \underline{10}. atol : 10. gb linksort : 2, \underline{3}, \underline{5}, 10. gb sorted : 2, \underline{3}, \underline{4}, 7, 8, 9, 10. j: \underline{2}, \underline{10}. k: \underline{5}, \underline{10}. key : \underline{2}, \underline{3}, 6, 7, 8, 9, 10. l: \underline{5}. link : \underline{2}, \underline{3}, 6, 7, 8, 9, 10. main: \underline{10}. malloc: 10. N: \underline{10}. node: \underline{2}, \underline{3}, 4, 5, 10. node struct: \underline{2}, \underline{3}. p: \underline{5}, \underline{10}. pp: \underline{5}, 6, 7, 8, 9. printf : 10. q: \underline{5}, \underline{10}. rand : 10.

⟨ Declarations 2, 4 ⟩ Used in section 1.

⟨ Partition the given list into 256 sublists alt sorted by low-order byte 6 ⟩ Used in section 5. ⟨ Partition the alt sorted lists into gb sorted by high-order byte 9 ⟩ Used in section 5. ⟨ Partition the alt sorted lists into gb sorted by second-lowest byte 7 ⟩ Used in section 5. ⟨ Partition the gb sorted lists into alt sorted by second-highest byte 8 ⟩ Used in section 5.

⟨ The gb linksort routine 5 ⟩ Used in section 1.

⟨ 10 ⟩ ⟨ 3 ⟩

RADIX SORT

Section Page

Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 Índice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 5