\input cwebmac
% quicksort: Um exemplo de CWEB baseado no exemplo wc de Silvio Levy
% e Donald E. Knuth
%
% Zé Augusto 8/98

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

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

\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{9in}
\setlength{\oddsidemargin}{-.125in}
\setlength{\evensidemargin}{-.125in}
\setlength{\textwidth}{6.75in}

\title{QuickSort}
\author{Zé Augusto}
\date{São Paulo, \today}

\begin{document}

\maketitle

\tableofcontents


\N{3}{1}Um exemplo de \texttt{CWEB}.  Este programa é uma implementação do
Quicksort. O programa lê um arquivo contendo inteiros e imprime os
mesmos em ordem crescente.

O programa está exagerada e desnecessariamente pulverizado e
comentado. O objetivo é dar mais exemplos das possibilidades do
\texttt{CWEB}.

\fi

\N{3}{2}Estrutura geral do programa.
A maioria dos programas \texttt{CWEB} têm uma estrutura comum.
Em geral, é uma boa idéia explicitar essa estrutura no início.
Nessa estrutura global, não precisamos incluir os \PB{$\#$ \&{define}} que são
incluídos automaticamente quando usamos os \PB{@\|d}.

Aqui vai a estrutra geral do \PB{\\{quicksort}} como definido por este programa
\texttt{CWEB} \PB{$\\{quicksort}.\|w$}:

\Y\B\X3:Arquivos a serem incluídos\X\6
\X5:Variáveis Globais\X\C{ só vamos usar variáveis globais quando
            realmente valer a pena }\6
\X13:Funções\X\6
\X6:Programa Principal\X\par
\fi

\M{3}Precisamos incluir as definições padrões de I/O.
Vamos incluir também o arquivo \PB{$\\{quicksort}.\|h$} que será criado por
este programa.
Essa inclusão é bastante artificial (desnecessária) para este programa.

\Y\B\4\X3:Arquivos a serem incluídos\X${}\E{}$\6
\8\#\&{include} \.{<stdio.h>}\6
\8\#\&{include} \.{"quicksort.h"}\par
\U2.\fi

\M{4} Como constantes em nosso programa vamos definir, como usual, o
\PB{\.{TRUE}} eo \PB{\.{FALSE}}. Além disso, vamos usar \PB{\.{MAX}} como o
número máximo
de elementos a serem ordenados.

Só para exemplificar o uso so \PB{@\|d}, vamos colocar a definição de
\PB{\.{TRUE}} no arquivo \PB{$\\{quicksort}.\|c$}, enquanto as definições de %
\PB{\.{FALSE}} e
\PB{\.{MAX}} irão para o arquivo \PB{$\\{quicksort}.\|h$}.

\Y\B\4\D$\.{TRUE}$ \5
\T{1}\par
\Y\B\4\X4:\.{quicksort.h }\X${}\E{}$\6
\8\#\&{define} \.{FALSE} \5\T{0}\6
\8\#\&{define} \.{MAX} \5\T{10000}\par
\A19.\fi

\M{5}
\Y\B\4\X5:Variáveis Globais\X${}\E{}$\C{ nenhuma variável a ser usada aqui. }%
\par
\U2.\fi

\N{3}{6}Quicksort.
Agora vamos definir o programa Quicksort em linhas gerais.

\Y\B\4\X6:Programa Principal\X${}\E{}$\6
\&{int} ${}\\{main}(\\{argc},\39\\{argv}){}$\1\1\6
\&{int} \\{argc};\C{ o número de argumentos na linha de comando do {\small
UNIX} }\6
\&{char} ${}{*}{*}\\{argv}{}$;\C{ os argumentos propriamente dito, um array de
strings }\2\2\6
${}\{{}$\5
\1\X12:Variáveis locais de \PB{\\{main}}\X\6
\X7:Verifica se o programa foi chamado corretamente\X\6
\X8:Leitura dos dados do arquivo\X\6
\X9:Ordenação propriamente dita\X\6
\X10:Impressão do vetor ordenado\X\6
\X11:Finalização\X\6
\4${}\}{}$\2\par
\U2.\fi

\M{7}Verifica os argumentos do programa e tenta abrir arquivo de entrada para
leitura.

\Y\B\4\X7:Verifica se o programa foi chamado corretamente\X${}\E{}$\6
\&{if} ${}(\\{argc}\I\T{2}){}$\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"Uso:\ quicksort\ <arq}\)\.{uivo>,\ "});{}$\6
${}\\{fprintf}(\\{stderr},\39\.{"onde\ <arquivo>\ e'\ u}\)\.{m\ arquivo\ de\
inteiro}\)\.{s\ a\ serem\ ordenados\\}\)\.{n"});{}$\6
\&{return} (\T{1});\6
\4${}\}{}$\2\6
${}\\{entrada}\K\\{fopen}(\\{argv}[\T{1}],\39\.{"r"}){}$;\C{ Abre <arquivo>
para leitura ("r" de read) }\6
\&{if} ${}(\\{entrada}\E\NULL){}$\5
${}\{{}$\C{ O arquivo nao existe }\1\6
${}\\{fprintf}(\\{stderr},\39\.{"Arquivo\ \%s\ nao\ enco}\)\.{ntrado\\n"},\39%
\\{argv}[\T{1}]);{}$\6
\&{return} (\T{1});\6
\4${}\}{}$\2\par
\U6.\fi

\M{8}\B\X8:Leitura dos dados do arquivo\X${}\E{}$\6
$\|n\K\T{0};{}$\6
\&{while} ${}(\R\\{feof}(\\{entrada})){}$\1\6
\&{if} ${}(\|n>\.{MAX}){}$\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"Número\ de\ inteiros\ }\)\.{a\ serem\
ordenados"});{}$\6
${}\\{fprintf}(\\{stderr},\39\.{"\ excede\ o\ limite\ de}\)\.{\ \%d\\n"},\39%
\.{MAX});{}$\6
\&{return} (\T{1});\6
\4${}\}{}$\2\6
\&{else} \&{if} ${}(\\{fscanf}(\\{entrada},\39\.{"\%d"},\39{\AND}\|v[\|n])>%
\T{0}){}$\1\5
${}\|n\PP{}$;\2\2\par
\U6.\fi

\M{9}\B\X9:Ordenação propriamente dita\X${}\E{}$\6
$\\{ordena}(\|v,\39\T{0},\39\|n-\T{1}){}$;\par
\U6.\fi

\M{10}A impressão será feita no arquivo padrão de saída e será feita com
um elemento em cada linha.
\Y\B\4\X10:Impressão do vetor ordenado\X${}\E{}$\6
\&{for} ${}(\|i\K\T{0};{}$ ${}\|i<\|n;{}$ ${}\|i\PP){}$\1\5
${}\\{fprintf}(\\{stdout},\39\.{"\%d\ \\n"},\39\|v[\|i]){}$;\2\par
\U6.\fi

\M{11}\B\X11:Finalização\X${}\E{}$\6
\\{fclose}(\\{entrada});\6
\&{return} (\T{0});\par
\U6.\fi

\M{12}Vamos agora definir as variáveis locais de \PB{\\{main}}.
Note que estou colocando estas definições depois do \PB{\\{main}} estar
"pronto". No \texttt{CWEB} podemos colocar nossas definições na ordem
em que julgamos ser a melhor para o entendimento do programa.


\Y\B\4\X12:Variáveis locais de \PB{\\{main}}\X${}\E{}$\6
\&{FILE} ${}{*}\\{entrada}{}$;\C{ arquivo contendo os inteiros a serem
ordenados }\6
\&{int} \|n${},{}$ \|v[\.{MAX}]${},{}$ \|i;\par
\U6.\fi

\M{13}Resta agora escrever as funções que fazem o trabalho de ordenação.
\Y\B\4\X13:Funções\X${}\E{}$\6
\X14:Função Ordena\X\6
\X17:Particiona\X\par
\U2.\fi

\M{14}Note que, finalmente, com a chegada do \texttt{CWEB}, como sempre
vocês quiseram fazer, agoram vocês podem respeitar o português e usar
acentos em nomes de variáveis, como \PB{\\{início}}, \PB{\\{pivô}} e \PB{%
\\{índice}}
abaixo!
Dêem uma olhada em como isso fica no arquivo \PB{$\\{quicksort}.\|c$}.

\Y\B\4\X14:Função Ordena\X${}\E{}$\6
\&{void} \\{ordena}(\&{int} \|v[\,]${},\39{}$\&{int} \\{início}${},\39{}$%
\&{int} \\{fim})\1\1\2\2\6
${}\{{}$\5
\1\X16:Variáveis locais de \PB{\\{ordena}}\X\6
\&{if} ${}(\\{início}<\\{fim}){}$\5
${}\{{}$\1\6
\X15:Escolha de um pivô\X\6
\\{índice}${}\K\\{particiona}(\|v,\39\\{início},\39\\{fim},\39\\{pivô});{}$\6
${}\\{ordena}(\|v,\39\\{início},\39\\{índice});{}$\6
${}\\{ordena}(\|v,\39\\{índice}+\T{1},\39\\{fim});{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U13.\fi

\M{15}Em termos de eficiência, se a seqüência dada é suposta ser uma
permutação aleatória dos dados de entrada, qualquer escolha de pivô
serve. Porém, com a função particiona que estamos usando, precisamos
escolher o primeiro elemento como pivô.

\Y\B\4\X15:Escolha de um pivô\X${}\E{}$\6
$\\{pivô}\K\\{início}{}$;\par
\U14.\fi

\M{16}\B\X16:Variáveis locais de \PB{\\{ordena}}\X${}\E{}$\6
\&{int} \\{pivô}${},{}$ \\{índice};\par
\U14.\fi

\N{3}{17}Particiona.
Usamos o algoritmo \PB{\\{Partition}} descrito no livro
\textit{Introduction to Algorithms} de Cormem, Leiserson e
Rivest.
Precisamos ser extremamente cuidadosos com o funcionamento desta
função.
Se o pivô é escolhido como o último elemento do segmento considerado
do vetor, o algoritmo pode entrar em \textit{loop}.
A função mantém a invariante que cada elemento em \PB{$\|v[\\{início}%
\MRL{{.}{.}}\|i-\T{1}]$} é
menor ou igual ao pivô e cada elemento em \PB{$\|v[\|j+\T{1}\MRL{{.}{.}}%
\\{fim}]$} é maior ou igual
ao pivô.

\Y\B\4\X17:Particiona\X${}\E{}$\6
\&{int} \\{particiona}(\&{int} \|v[\,]${},\39{}$\&{int} \\{início}${},\39{}$%
\&{int} \\{fim}${},\39{}$\&{int} \\{pivô})\1\1\2\2\6
${}\{{}$\5
\1\X18:Variáveis locais de \PB{\\{particiona}}\X\6
${}\\{valor}\K\|v[\\{pivô}];{}$\6
${}\|i\K\\{início};{}$\6
${}\|j\K\\{fim};{}$\6
\&{while} (\.{TRUE})\5
${}\{{}$\1\6
\&{while} ${}(\|v[\|i]<\\{valor}){}$\1\5
${}\|i\PP;{}$\2\6
\&{while} ${}(\\{valor}<\|v[\|j]){}$\1\5
${}\|j\MM;{}$\2\6
\&{if} ${}(\|i<\|j){}$\5
${}\{{}$\C{ Fazemos a troca. }\1\6
${}\\{aux}\K\|v[\|i];{}$\6
${}\|v[\|i]\K\|v[\|j];{}$\6
${}\|v[\|j]\K\\{aux};{}$\6
${}\|i\PP;{}$\6
${}\|j\MM;{}$\6
\4${}\}{}$\2\6
\&{else}\1\5
\&{return} (\|j);\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U13.\fi

\M{18}\B\X18:Variáveis locais de \PB{\\{particiona}}\X${}\E{}$\6
\&{int} \\{aux}${},{}$ \\{valor}${},{}$ \|i${},{}$ \|j;\par
\U17.\fi

\M{19}Vamos incluir em \PB{$\\{quicksort}.\|h$} os protótipos das funções.

\Y\B\4\X4:\.{quicksort.h }\X${}\mathrel+\E{}$\6
\&{void} ${}\\{ordena}(\&{int}[\,],\39\&{int},\39\&{int});{}$\6
\&{int} ${}\\{particiona}(\&{int}[\,],\39\&{int},\39\&{int},\39\&{int}){}$;\par
\fi

\M{20}

\cwebIndexIntro{%
Aqui vai uma lista de identificadores usados e onde eles aparecem.
Entradas grifadas indicam os lugares de definições. Mensagens de erros
também são mostradas.
}

\end{document}
\fi

\inx
\fin
\con
