\input cwebmac
\def\title{RADIX\_\,SORT}
\input acentos


\N{1}{1}Introdução.  Esta é uma adaptação de um código escrito por Knuth
[D.$\,$E.~Knuth, {\sl The Stanford GraphBase: a Platform for Combinatorial
Computing}, (New York: ACM Press, 1993), viii+576pp.  Co-publicado pela
Addison--Wesley Publishing Company, ISBN 0-201-54275-7; Veja o módulo {\tt
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).

\Y\B\8\#\&{include} \.{<stdio.h>}\C{ o ponteiro \.{NULL} (\PB{$\NULL$}) é
definido aqui }\7
\X2:Declarations\X\6
\X5:The \PB{\\{gb\_linksort}} routine\X\par
\fi

\M{2}A rotina de maior interesse aqui é uma rotina chamada \PB{\\{gb%
\_linksort}(\,)} que
ordena (reorganiza) os elementos de uma lista ligada em ordem decrescente de
seus campos \PB{\\{key}}, que é um \PB{\&{long}}.  Assumimos que estes campos %
\PB{\\{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: \PB{\\{gb\_sorted}[\T{127}]}, \PB{\\{gb\_sorted}[\T{126}]}, %
\dots, \PB{\\{gb\_sorted}[\T{0}]}.
Para examinar os elementos em ordem decrescente de suas chaves, podemos varrer
os elementos com rotinas como a seguinte:
$$\vcenter{\halign{#\hfil\cr
\PB{$\{$}\cr
\quad\PB{\&{int} \|j;}\cr
\quad\PB{$\\{node}*\|p;$}\cr
\noalign{\smallskip}
\quad\PB{\&{for} ${}(\|j\K\T{127};{}$ ${}\|j\G\T{0};{}$ ${}\|j\MM)$}\cr
\qquad\PB{\&{for} ${}(\|p\K\\{gb\_sorted}[\|j];{}$ \|p; ${}\|p\K\|p\MG%
\\{link})$}\cr
\qquad\qquad\\{look\_at}\PB{(\|p)};\cr
\PB{$\}$}\cr}}$$
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}\le\PB{\\{key}}<(j+1)2^{24}$ vão aparecer na lista \PB{\\{gb\_sorted}[%
\|j]}.  Portanto,
o resultado pode ser encontrado inteiramente contido na lista \PB{\\{gb%
\_sorted}[\T{0}]}
se todas as chaves são estritamente menores que~$2^{24}$.

\Y\B\4\X2:Declarations\X${}\E{}$\6
\&{typedef} \&{struct} \&{node\_struct} ${}\{{}$\1\6
\&{long} \\{key};\C{ quantidade numérica, que deve ser não-negativa }\6
\&{struct} \&{node\_struct} ${}{*}\\{link}{}$;\C{ apontador para o próximo
elemento da lista }\2\6
${}\}{}$ \&{node};\C{ estes serão os elementos da lista a ser processada }\par
\A4.
\U1.\fi

\M{3}Aqui está o header file que os usuários deste módulo devem usar.

\Y\B\4\X3:\.{radix.h }\X${}\E{}$\6
\&{typedef} \&{struct} \&{node\_struct} ${}\{{}$\1\6
\&{long} \\{key};\C{ quantidade numérica, que deve ser não-negativa }\6
\&{struct} \&{node\_struct} ${}{*}\\{link}{}$;\C{ apontador para o próximo
elemento da lista }\2\6
${}\}{}$ \&{node};\C{ estes serão os elementos da lista a ser processada }\6
\&{extern} \&{void} \\{gb\_linksort}(\,);\C{ procedure to sort a linked list }\6
\&{extern} \&{node} ${}{*}\\{gb\_sorted}[\,]{}$;\C{ the results of \PB{\\{gb%
\_linksort}} }\par
\fi

\M{4}Faremos 4 passadas do radix sort, com {\it radix\/} (base) 256.
(Veja, por exemplo, Algoritmo~5.2.5R in {\sl Sorting and Searching}, de
Knuth).  Nós movemos os elementos da lista entre dois vetores de listas: os
vetores \PB{\\{gb\_sorted}} (que conterá o resultado final) e \PB{\\{alt%
\_sorted}} (que
conterá resultados intermediários).

\Y\B\4\X2:Declarations\X${}\mathrel+\E{}$\6
\&{node} ${}{*}\\{gb\_sorted}[\T{256}]{}$;\C{ vetor de listas, para as passadas
pares }\6
\&{static} \&{node} ${}{*}\\{alt\_sorted}[\T{256}]{}$;\C{ vetor auxiliar, para
as passadas ímpares }\par
\fi

\M{5}Aqui estão as 4 passadas.

\Y\B\4\X5:The \PB{\\{gb\_linksort}} routine\X${}\E{}$\6
\&{void} \\{gb\_linksort}(\|l)\1\1\6
\&{node} ${}{*}\|l;\2\2{}$\6
${}\{{}$\5
\1\&{register} \&{long} \|k;\C{ índice para a lista-destino }\6
\&{register} \&{node} ${}{*}{*}\\{pp}{}$;\C{ ponto corrente na lista de
ponteiros }\6
\&{register} \&{node} ${}{*}\|p,{}$ ${}{*}\|q{}$;\C{ ponteiros para manipulação
de listas }\7
\X6:Partition the given list into 256 sublists \PB{\\{alt\_sorted}} by
low-order byte\X;\6
\X7:Partition the \PB{\\{alt\_sorted}} lists into \PB{\\{gb\_sorted}} by
second-lowest byte\X;\6
\X8:Partition the \PB{\\{gb\_sorted}} lists into \PB{\\{alt\_sorted}} by
second-highest byte\X;\6
\X9:Partition the \PB{\\{alt\_sorted}} lists into \PB{\\{gb\_sorted}} by
high-order byte\X;\6
\4${}\}{}$\2\par
\U1.\fi

\M{6}\B\X6:Partition the given list into 256 sublists \PB{\\{alt\_sorted}} by
low-order byte\X${}\E{}$\6
\&{for} ${}(\\{pp}\K\\{alt\_sorted}+\T{255};{}$ ${}\\{pp}\G\\{alt\_sorted};{}$
${}\\{pp}\MM){}$\1\5
${}{*}\\{pp}\K\NULL{}$;\C{ inicializamos todas as listas-destino }\2\6
\&{for} ${}(\|p\K\|l;{}$ \|p; ${}\|p\K\|q){}$\5
${}\{{}$\1\6
${}\|k\K\|p\MG\\{key}\AND\T{\^ff}{}$;\C{ extraímos os oito bits menos
significantivos }\6
${}\|q\K\|p\MG\\{link};{}$\6
${}\|p\MG\\{link}\K\\{alt\_sorted}[\|k];{}$\6
${}\\{alt\_sorted}[\|k]\K\|p;{}$\6
\4${}\}{}$\2\par
\U5.\fi

\M{7}Agora vamos ler as listas de \PB{\\{alt\_sorted}} de 0 a 255, e vamos
classificar os
elementos de acordo com o segundo byte menos significativo.

\Y\B\4\X7:Partition the \PB{\\{alt\_sorted}} lists into \PB{\\{gb\_sorted}} by
second-lowest byte\X${}\E{}$\6
\&{for} ${}(\\{pp}\K\\{gb\_sorted}+\T{255};{}$ ${}\\{pp}\G\\{gb\_sorted};{}$
${}\\{pp}\MM){}$\1\5
${}{*}\\{pp}\K\NULL{}$;\C{ inicializamos todas as listas-destino }\2\6
\&{for} ${}(\\{pp}\K\\{alt\_sorted};{}$ ${}\\{pp}<\\{alt\_sorted}+\T{256};{}$
${}\\{pp}\PP){}$\1\6
\&{for} ${}(\|p\K{*}\\{pp};{}$ \|p; ${}\|p\K\|q){}$\5
${}\{{}$\1\6
${}\|k\K(\|p\MG\\{key}\GG\T{8})\AND\T{\^ff}{}$;\C{ extraímos os proximos oito
bits }\6
${}\|q\K\|p\MG\\{link};{}$\6
${}\|p\MG\\{link}\K\\{gb\_sorted}[\|k];{}$\6
${}\\{gb\_sorted}[\|k]\K\|p;{}$\6
\4${}\}{}$\2\2\par
\U5.\fi

\M{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!)

\Y\B\4\X8:Partition the \PB{\\{gb\_sorted}} lists into \PB{\\{alt\_sorted}} by
second-highest byte\X${}\E{}$\6
\&{for} ${}(\\{pp}\K\\{alt\_sorted}+\T{255};{}$ ${}\\{pp}\G\\{alt\_sorted};{}$
${}\\{pp}\MM){}$\1\5
${}{*}\\{pp}\K\NULL{}$;\C{ inicializamos todas as listas-destino }\2\6
\&{for} ${}(\\{pp}\K\\{gb\_sorted}+\T{255};{}$ ${}\\{pp}\G\\{gb\_sorted};{}$
${}\\{pp}\MM){}$\1\6
\&{for} ${}(\|p\K{*}\\{pp};{}$ \|p; ${}\|p\K\|q){}$\5
${}\{{}$\1\6
${}\|k\K(\|p\MG\\{key}\GG\T{16})\AND\T{\^ff}{}$;\C{ extraímos os proximos oito
bits }\6
${}\|q\K\|p\MG\\{link};{}$\6
${}\|p\MG\\{link}\K\\{alt\_sorted}[\|k];{}$\6
${}\\{alt\_sorted}[\|k]\K\|p;{}$\6
\4${}\}{}$\2\2\par
\U5.\fi

\M{9}Os 8 bits mais significativos corresponderão a números entre 0 e 127,
porque
assumimos que os campos \PB{\\{key}} são inteiros menores que $2^{31}$.  (Uma
rotina
similar funcionaria para \PB{\&{int}}, ou \PB{\&{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.)

\Y\B\4\X9:Partition the \PB{\\{alt\_sorted}} lists into \PB{\\{gb\_sorted}} by
high-order byte\X${}\E{}$\6
\&{for} ${}(\\{pp}\K\\{gb\_sorted}+\T{255};{}$ ${}\\{pp}\G\\{gb\_sorted};{}$
${}\\{pp}\MM){}$\1\5
${}{*}\\{pp}\K\NULL{}$;\C{ inicializamos todas as listas-destino }\2\6
\&{for} ${}(\\{pp}\K\\{alt\_sorted};{}$ ${}\\{pp}<\\{alt\_sorted}+\T{256};{}$
${}\\{pp}\PP){}$\1\6
\&{for} ${}(\|p\K{*}\\{pp};{}$ \|p; ${}\|p\K\|q){}$\5
${}\{{}$\1\6
${}\|k\K(\|p\MG\\{key}\GG\T{24})\AND\T{\^ff}{}$;\C{ extraímos os oito bits mais
significativos }\6
${}\|q\K\|p\MG\\{link};{}$\6
${}\|p\MG\\{link}\K\\{gb\_sorted}[\|k];{}$\6
${}\\{gb\_sorted}[\|k]\K\|p;{}$\6
\4${}\}{}$\2\2\par
\U5.\fi

\M{10}Aqui está um programa muito simples para ilustrar o uso da rotina
\PB{\\{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 \PB{\\{rand}(\,)} e os coloca em uma lista ligada.
Esta
lista ligada é então fornecida como argumento em uma chamada de
\PB{\\{gb\_linksort}(\,)}.  A saída do programa é a lista de números gerados em
ordem
decrescente.

\Y\B\4\X10:\.{driver.c }\X${}\E{}$\6
\8\#\&{include} \.{<stdio.h>}\6
\8\#\&{include} \.{<stdlib.h>}\6
\8\#\&{include} \.{"radix.h"}\6
\&{int} \\{main}(\&{int} \\{argc}${},\39{}$\&{char} ${}{*}\\{argv}[\,]){}$\1\1%
\2\2\6
${}\{{}$\1\6
\&{long} \|j${},{}$ \|k${},{}$ \|N${}\K\\{atol}(\\{argv}[\T{1}]);{}$\6
\&{node} ${}{*}\|p,{}$ ${}{*}\|q;{}$\7
${}\|p\K\NULL;{}$\6
\&{while} ${}(\|N\MM>\T{0}){}$\5
${}\{{}$\1\6
${}\|q\K{}$(\&{node} ${}{*}){}$ \\{malloc}(\&{sizeof}(\&{node}));\6
${}\|q\MG\\{key}\K\\{rand}(\,);{}$\6
${}\|q\MG\\{link}\K\|p;{}$\6
${}\|p\K\|q;{}$\6
\4${}\}{}$\2\6
\\{gb\_linksort}(\|p);\6
\&{for} ${}(\|j\K\T{127};{}$ ${}\|j\G\T{0};{}$ ${}\|j\MM){}$\5
${}\{{}$\1\6
\&{for} ${}(\|p\K\\{gb\_sorted}[\|j];{}$ \|p; ${}\|p\K\|p\MG\\{link}){}$\1\5
${}\\{printf}(\.{"\%ld\\n"},\39\|p\MG\\{key});{}$\2\6
\4${}\}{}$\2\6
\&{return} \T{0};\6
\4${}\}{}$\2\par
\fi

\N{1}{11}Índice.  Aqui estão os identificadores usados neste programa, com seus
respectivos locais de definição e uso.
\fi

\inx
\fin
\con
