\input cwebmac
\documentclass[language=brazil,structure=flat]{cweb}

%% Isto é um comentário.

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
%----------------------------

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Dimensão da página
\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{9in}
\setlength{\oddsidemargin}{-.125in}
\setlength{\evensidemargin}{-.125in}
\setlength{\textwidth}{6.75in}

%%% Este tal de \newcommand é a macro do LaTeX.
\newcommand{\cweb}{\texttt{CWEB}}

\begin{document}

\title{Ordenação por Inserção}
\author{Paulo Feofiloff}
\date{São Paulo,  2 de março de 2001}

\maketitle
\tableofcontents


\N{2}{1}Introdução.
Esta é uma demonstração do sistema \cweb\ Knuth e Levy
(veja \texttt{http://www.ime.usp.br/\~{}pf/CWEB/}).
Um programa \cweb, como este que você está lendo,
é uma espécie de jogo de armar que produz um programa C.
Ele contém {\it (1)} vários ``blocos'' de código C e
{\it (2)} instruções sobre a maneira de encaixar esses blocos
para construir o programa.

O leitor pode usar este pequeno exemplo como ponto de partida
para escrever os seus próprios programas \cweb.


\fi

\N{3}{2}O que o programa faz.
Este programa coloca em ordem crescente qualquer seqüência de números inteiros.
A seqüência é dada em um arquivo, e o resultado é gravado em outro arquivo.
O usuário deve indicar os nomes dos arquivos
(o segundo pode ser igual ao primeiro)
na linha de comando.
Eis um exemplo de linha de comando que ativa o programa:
\vskip 5pt
\centerline{\tt isort dados.txt resultados.txt}


\fi

\N{3}{3}Referências.
O programa usa o bem-conhecido algoritmo de ordenação-por-inserção
(= insertion sort).
Minha inspiração é o programa 6.3 (p.264) do livro
{\it Algorithms in C} (3rd.\ ed., Addison-Wesley, 1998)
de R. Sedgewick.
Pode ser um exagero dar referências para um programa tão simples,
mas em geral é importante citar suas fontes.


\fi

\N{2}{4}Insertion sort.
Ao contrário de um programa C crú, um programa \cweb\
pode ir direto ao assunto central
e deixar os assuntos burocráticos e administrativos
(entrada, saída, include, define, declaração de variáveis, etc.)
para mais tarde.

A função \PB{\\{isort}} rearranja os elementos de um vetor \PB{$\|a[\|l%
\MRL{{.}{.}}\|r]$}
de modo que ele fique em ordem crescente, ou seja,
de modo que tenhamos $a[l] \leq a[l+1] \leq \cdots \leq a[r]$.
% Note que o algoritmo funciona corretamente mesmo em casos extremos:
% quando l == r, quando l == r+1,
% quando todos os elementos do vetor têm o mesmo valor, etc.

\Y\B\4\X4:Função \PB{\\{isort}}\X${}\E{}$\6
\&{void} \\{isort}(\&{int} \|a[\,]${},\39{}$\&{int} \|l${},\39{}$\&{int} \|r)\1%
\1\2\2\6
${}\{{}$\1\6
\&{int} \|i;\7
\&{for} ${}(\|i\K\|l+\T{1};{}$ ${}\|i\Z\|r;{}$ ${}\|i\PP{}$)\1\6
\X5:Execute uma iteração\X\2\6
\4${}\}{}$\2\par
\U8.\fi

\M{5}Para entender como o algoritmo funciona,
basta entender que no início de cada iteração o subvetor
\vskip 3pt
\centerline{\PB{$\|a[\|l\MRL{{.}{.}}\|i-\T{1}]$} está em ordem crescente.}
\vskip 7pt
\noindent
Esta propriedade é trivialmente verdadeira quando \PB{$\|i\E\|l+\T{1}$}.
Quando \PB{\|i} atingir o valor \PB{$\|r+\T{1}$}, o vetor \PB{$\|a[\|l%
\MRL{{.}{.}}\|r]$} estará ordenado!

\Y\B\4\X5:Execute uma iteração\X${}\E{}$\6
${}\{{}$\1\6
\&{int} \|j${}\K\|i,{}$ \|v${}\K\|a[\|i];{}$\7
\&{while} ${}(\|j>\|l\W\|v<\|a[\|j-\T{1}]){}$\5
${}\{{}$\1\6
${}\|a[\|j]\K\|a[\|j-\T{1}];{}$\6
${}\|j\MM;{}$\6
\4${}\}{}$\2\6
${}\|a[\|j]\K\|v;{}$\6
\4${}\}{}$\2\par
\U4.\fi

\M{6}O símbolo \PB{$\W$} que aparece em ``\PB{\&{while} ${}(\|j>\|l\W\|v<\|a[%
\|j-\T{1}])$}''
representa o operador lógico {\&\&}.
No programa C gerado a partir deste programa \cweb\
teremos ``{while (j > l \&\& v < a[j-1])}''.


\fi

\N{3}{7}Geração do header file {isort.h}.
Vou gerar um header file {isort.h}, que servirá de interface para
outros programas que porventura queiram usar minha função \PB{\\{isort}}.
% (Se não me engano, o ``\PB{\&{extern}}'' é dispensável.)

\Y\B\4\X7:\.{isort.h }\X${}\E{}$\6
\&{extern} \&{void} ${}\\{isort}(\&{int}[\,],\39\&{int},\39\&{int}){}$;\par
\fi

\N{2}{8}Estrutura geral do programa e função main.
A estrutura do programa {isort.c} gerado por este programa \cweb\
é muito simples.
Como freqüentemente acontece, os assuntos administrativos
(entrada de dados, gravação de resultados, etc.)
consomem mais espaço que a parte ``importante'' do programa.

\Y\B\X16:Inclusão de header files\X\6
\X4:Função \PB{\\{isort}}\X\7
\&{int} \\{main}(\&{int} \\{numargs}${},\39{}$\&{char} ${}{*}\\{arg}[\,]){}$\1%
\1\2\2\6
${}\{{}$\1\6
\X13:Variáveis locais da \PB{\\{main}}\X\6
\X9:Processamento da linha de comando\X\6
\X10:Entrada de \PB{\|n} e \PB{$\|a[\T{0}\MRL{{.}{.}}\|n-\T{1}]$}\X\6
${}\\{isort}(\|a,\39\T{0},\39\|n-\T{1});{}$\6
\X14:Gravação dos resultados\X\6
\&{return} \T{0};\6
\4${}\}{}$\2\par
\fi

\M{9}É preciso verificar se o usuário digitou
o número correto de argumentos na linha de comando.

\Y\B\4\X9:Processamento da linha de comando\X${}\E{}$\6
\&{if} ${}(\\{numargs}\I\T{3}){}$\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"\\nUso:\ isort\ <nomea}\)\.{rq1>\
<nomearq2>"});{}$\6
${}\\{fprintf}(\\{stderr},\39\.{"\\n\ \ \ \ \ <nomearq1>\ é}\)\.{\ o\ nome\ do\
arquivo\ d}\)\.{e\ dados"});{}$\6
${}\\{fprintf}(\\{stderr},\39\.{"\\n\ \ \ \ \ <nomearq2>\ é}\)\.{\ o\ nome\ do\
arquivo\ d}\)\.{e\ resultados\\n"});{}$\6
\&{return} ${}{-}\T{1};{}$\6
\4${}\}{}$\2\par
\U8.\fi

\M{10}\B\X10:Entrada de \PB{\|n} e \PB{$\|a[\T{0}\MRL{{.}{.}}\|n-\T{1}]$}\X${}%
\E{}$\6
$\\{arq}\K\\{fopen}(\\{arg}[\T{1}],\39\.{"r"});{}$\6
\&{if} ${}(\\{arq}\E\NULL){}$\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"\\nNão\ encontrei\ arq}\)\.{uivo\ \%s\\n"},\39%
\\{arg}[\T{1}]);{}$\6
\&{return} ${}{-}\T{1};{}$\6
\4${}\}{}$\2\6
\X12:Leitura de \PB{\\{arq}}\X;\6
\\{fclose}(\\{arq});\par
\U8.\fi

\M{11}O símbolo \PB{$\NULL$} que aparece acima em ``\PB{\&{if} ${}(\\{arq}\E%
\NULL)$}''
é a representação de {NULL}.
No programa C gerado a partir deste programa \cweb
teremos ``{if (arq == NULL)}''.



\fi

\M{12}O processo de leitura preenche o vetor \PB{$\|a[\T{0}\MRL{{.}{.}}\|n-%
\T{1}]$}
e determina o valor de \PB{\|n}.
A leitura termina quando chega ao fim do arquivo ou
quando encontra algo incompatível com o formato {\%d}.
Convém lembrar que a expressão \PB{$\\{fscanf}(\\{arq},\|f,\,\ldots\,)$} tem
valor igual
ao número de itens que foi possível extrair de \PB{\\{arq}}
de acordo com o formato \PB{\|f}.

\Y\B\4\X12:Leitura de \PB{\\{arq}}\X${}\E{}$\6
$\|n\K\T{0};{}$\6
\&{while} ${}(\\{fscanf}(\\{arq},\39\.{"\%d"},\39{\AND}\|a[\|n])\E\T{1}){}$\5
${}\{{}$\1\6
${}\PP\|n;{}$\6
\&{if} ${}(\|n>\.{MAX}){}$\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"\\nNão\ sei\ lidar\ com}\)\.{\ mais\ que\ \%d\
números}\)\.{\\n"},\39\.{MAX});{}$\6
\&{return} ${}{-}\T{1};{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U10.\fi

\M{13}Meu programa está preparado para lidar com no máximo \PB{\.{MAX}}
números.
Convém que \PB{\.{MAX}} não passe de algumas centenas,
pois o algoritmo de ordenação-por-inserção é lento.
Vou reservar espaço para \PB{$\.{MAX}+\T{1}$} números no vetor \PB{\|a},
pois o código do bloco anterior parece exigir essa ``margem de segurança''.

\Y\B\4\D$\.{MAX}$ \5
\T{1000}\par
\Y\B\4\X13:Variáveis locais da \PB{\\{main}}\X${}\E{}$\6
\&{FILE} ${}{*}\\{arq};{}$\6
\&{int} \|n${},{}$ ${}\|a[\.{MAX}+\T{1}]{}$;\par
\A15.
\U8.\fi

\M{14}A seqüência ordenada será gravada no arquivo \PB{\\{arg}[\T{2}]}.

\Y\B\4\X14:Gravação dos resultados\X${}\E{}$\6
$\\{arq}\K\\{fopen}(\\{arg}[\T{2}],\39\.{"w"});{}$\6
\&{if} ${}(\\{arq}\E\NULL){}$\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"\\nSocorro!\ Não\ cons}\)\.{igo\ abrir\
arquivo\ \%s}\)\.{\\n"},\39\\{arg}[\T{2}]);{}$\6
\&{return} ${}{-}\T{1};{}$\6
\4${}\}{}$\2\6
\&{for} ${}(\|i\K\T{0};{}$ ${}\|i<\|n;{}$ ${}\PP\|i){}$\1\5
${}\\{fprintf}(\\{arq},\39\.{"\%d\\n"},\39\|a[\|i]);{}$\2\6
\\{fclose}(\\{arq});\par
\U8.\fi

\M{15}A seção acima usou mais uma variável local.

\Y\B\4\X13:Variáveis locais da \PB{\\{main}}\X${}\mathrel+\E{}$\6
\&{int} \|i;\par
\fi

\N{3}{16}Inclusão de header files.
O header file {stdio.h} contém
os protótipos das funções de entrada e saída
e a definição do arquivo de erros \PB{\\{stderr}}.

\Y\B\4\X16:Inclusão de header files\X${}\E{}$\6
\8\#\&{include} \.{<stdio.h>}\par
\U8.\fi

\M{17}Agora que terminei, estou vendo que o programa ficou
muito fragmentado (grande número de pequenos blocos)
e excessivamente comentado.
Mas vou deixar as coisas assim mesmo;
afinal, esse programa é apenas um exemplo despretensioso!


\cwebIndexIntro{%
Para cada identificador,
este índice cita as seções onde o identificador é
definido (nú\-me\-ros grifados) ou usado.
No caso de identificadores com uma só letra, como \PB{\|v},
somente as seções que contêm as definições são citadas.
É claro que este índice é gerado automaticamente.
}

\fi

\M{18}
\end{document}






\fi


\inx
\fin
\con
