path: root/macros/generic/laansort/sort.tex

%Contents: Sorting via TeX (heap and quick)             %Submission CTAN
%          Introduced at TUG 93.
%Version:  1.0 December 1993.
%Purpose:  Sorting within TeX.
%Example of use (after \input sort.tex %the auxiliaries
%                      \input heap.tex resp. quick.tex %the macros)
%Documentation: Proceedings TUG 93, Aston, TUGboat 14.3, (abridged)
%                                      and MAPS 93.1     (complete)
%C.G. van der Laan, Hunzeweg 57, 9893PB, Garnwerd. Holland. 05941-1525.
%                                                      cgl@risc1.rug.nl
%For TeX-ing this contribution use ltugproc.sty; the macros can be used
%with AllTeX.
%This file contains
% - History of changes
% - Auxiliaries (sort.tex)
% - heap.tex
% - quick.tex
% - Example heap sort
% -         quick sort
%
%%%%%%%%%% History of changes    %%%%%%%%%%
%History of change files
%Jan 1994: Submission CTAN.
%
%Next follows the two appendices as supplied in TUGboat 14, 3 with the macros
%included, so that it can be processed by ltugproc.sty
\documentstyle{ltugproc}
\title{Sorting macros}
\author{Kees van der Laan}
\address{Hunzeweg 57, 9893 PB, Garnwerd, The Netherlands}
\netaddress[\network{Internet}]{cgl@risc1.rug.nl}
\begin{abstract} The macros as submitted for CTAN.
They are embedded in an article which consists of the appendices
heap sort and quick sort.
The latter show the low level use of the (worker) macros.
For high level use see the article in TUGBoat 14, 3,  (TUG 93) or
the complete---Sorting in BLUe---as released in MAPS 93.1.
\end{abstract}
\maketitle
\let\ftn\footnote
\begin{document}
\noindent Contents of file\\
- sort.tex (auxiliaries)\\
- heap.sort (specific for heap sort)\\
- quick.sort (specific for quick sort)\\
- the two appendices.

\vfill\eject
%
%%%%%%%%%% Auxiliaries sort.tex  %%%%%%%%%%
%Sort tex macros%sort.tex                        Jan 93
%Shorthands
\let\ag=\aftergroup
\let\ea=\expandafter\let\nx=\noexpand
%Counters
\newcount\n\newcount\k\newcount\kk\n=0
\newcount\kzero\kzero0 %Bias value
\newcount\pk\newcount\pkone%Used in sortcs
\newcount\frst%First value of range
\newcount\lst %Last value of range
\newcount\slst%Successor \lst
\newcount\dif %Difference \lst-\frst
\newcount\nw  %Number of words
\newcount\nc  %Number of characters/comp
\newcount\numex %Number of exchanges
\newcount\rndval%Random number
\newcount\rndnum%Seed random generator
\newcount\rndtmp%Temporary value
\newcount\status%Status comparison
%Newif-s
\newif\ifcontinue%controls loops
\newif\iffound%locating accent cs
\newif\ifproof\prooftrue
%
%Storing: from copy
\def\seq#1\qes{\k0 \fifow#1 \wofif{} }
%Auxiliaries: FIFO
\def\fifow#1 {\ifx\wofif#1\n\k\wofif\fi
 \processw{#1}\fifow}
\def\wofif#1\fifow{\fi}
\def\processw#1{\advance\k1 \ea
 \gdef\csname\the\k\endcsname{#1}}
%
%Storing: from file
\newread\rec
\def\storefrom#1{%#1 is file name
 \openin\rec=#1 \k\kzero \continuetrue
 \loop\ifeof\rec\continuefalse\fi
 \ifcontinue\advance\k1{}\read\rec to\xyz
  \ea\let\csname\the\k\endcsname=\xyz
 \repeat\advance\k-1\n\k\closein\rec}
%
%Storing: random numbers
\def\storerandomn#1{%#1 number of numbers
 \n#1\k0
 \loop\ifnum\k<\n\advance\k1 \rnd\ea
  \xdef\csname\the\k\endcsname{\the\rndval}
 \repeat}
%
%With, due to Reid, 1987
\def\rnd{\global\multiply\rndnum371{}%
 \global\advance\rndnum1{}%
 \ifnum\rndnum>99999
  \rndtmp\rndnum \divide\rndtmp100000
  \multiply\rndtmp100000
  \global\advance\rndnum-\rndtmp
 \fi\global\rndval\rndnum
 \global\divide\rndval1000 }
%
%Storing: random words
\def\storerandomw#1{%#1 number of words
 \n#1\nw\n\def\defarr{\ea\gdef
  \csname\the\nw\endcsname}
 {\loop\ifnum0<\nw{\ag\defarr\ag{%
   \randomword}}\advance\nw-1
 \repeat}}%end s-r-w.
%
\def\randomword{\rnd \nc\rndval
 \divide\nc15 \advance\nc2
 \loop\ifnum0<\nc\randomchar
   \advance\nc-1
 \repeat}%end r-word
%
%Random character is modified
\def\randomchar{\rnd
 \multiply\rndval29 \divide\rndval100
 \ifnum26=\rndval\rndval0 \fi
 \ifnum26<\rndval\rndval4 \fi
%Mod cgl: I \ag-ed the letter
\ea\ag\ifcase\rndval
 a\or b\or c\or d\or e\or f\or g\or h\or
 i\or j\or k\or l\or m\or n\or o\or p\or
 q\or r\or s\or t\or u\or v\or w\or x\or
 y\or z\fi}%end r-char
%
%Typeset
%Parameters: Separators
\def\sepn{, }%Number separator
\def\sepw{ } %Word separator
\let\sep\sepw
%
\def\prc#1{\init{#1}\def\prc##1{%
 \ifnum\lst=##1{}\else\ifnum\slst=##1{}%
  \lst\slst\advance\slst1{}\else
  \prtfl\sepn\init{##1}\fi\fi}}
%
\def\init#1{\frst=#1\lst=#1\slst=#1{}%
   \advance\slst1{}}
%
%Print range: \frst-\lst (or \lst).
\def\prtfl{\the\frst\ifnum\frst<\lst
 \advance\frst1{}\ifnum\frst=\lst\sepn
 \else\nobreak--\nobreak\fi\the\lst\fi}
%
%Printing sequences
\def\prts{{\k\kzero%print \1,...\n
 \def\sep{\let\sep=\sepw}%
 \loop\ifnum\k<\n\advance\k1
  \sep\csname\the\k\endcsname
 \repeat}}%end \prts
%
\let\prtw=\prts
%
\def\prtn{{\k\kzero%Print number sequence
 \loop\ifnum\k<\n\advance\k1
  \ea\prc\csname\the\k\endcsname
 \repeat\prtfl}}%end \prtn
%
\def\typind#1{%#1 a def
 \ea\splittot#1.%
 \ifcase\digit\word\or
         {\tt\word}\or
  {\tt\char92\word}\or
  $\langle\hbox{\word}\rangle$\fi{}
  \pagenrs}
%
\def\splittot#1 !#2 #3.{\def\word{#1}%
  \chardef\digit=#2{}\def\pagenrs{#3}}
%
\def\prtind{{\def\\{\hfil\break}\k\kzero
 \def\sep{\let\sep\sepw}%
 \loop\ifnum\k<\n\advance\k1
  \sep\ea\typind\csname\the\k\endcsname
 \repeat}}
%
%Sorting in O(nlog n)
%Numbers
\def\sortn{\let\cmp\cmpn\sort\prtn}
%
%ASCII words
\def\sortaw{\let\cmp\cmpaw\sort\prtw}
%
%Words (with accents)
\def\sortw{\let\cmp\cmpw{\accdef\sort}\prtw}
%
\def\sort{\heapsort}
%
%Paramaters: ij and accent string
\def\accstr{\`\'\"\^\c}
%
\def\accdef{\def\i{i}\def\j{j}%
 \def\'##1{##1a}\def\`##1{##1g}%
 \def\"##1{##1t}\def\^##1{##1h}%
 \def\c##1{##1c}}
%
\def\ij{ij}
%
%Sorting parameters: exchange macro
\def\xch#1#2{%#1, #2 counter variables
 \ea\let\ea\auxone\csname\the#1\endcsname
 \ea\let\ea\auxtwo\csname\the#2\endcsname
 \ea\global\ea\let\csname\the#2\endcsname
 \auxone
 \ea\global\ea\let\csname\the#1\endcsname
 \auxtwo}
%
%Sorting parameters: number comparison
\def\cmpn#1#2{%#1, #2 are def-s
%Result: \status= 0, 1, 2, if
%        \val{#1} =, >, < \val{#2}
 \ifnum#1=#2\global\status0 \else
   \ifnum#1>#2\global\status1 \else
                \global\status2 \fi\fi}
%
%Parameters: comparison of words
\def\cmpw#1#2{%#1, #2 are def-s
%Result: \status= 0, 1, 2, if
%        \val{#1} =, >, < \val{#2}
 \let\nxt\nxtw\cmpc#1#2}
%
\def\cmpaw#1#2{%#1, #2 are defs with as
%replacement text the words.
%Result: \status= 0, 1, 2, if
%        \val{#1} =, >, < \val{#2}
 \let\nxt\nxtaw\cmpc#1#2}
%
\def\cmpc#1#2{%#1, #2 are def-s
%Result: \status= 0, 1, 2, if
%        \val{#1} =, >, < \val{#2}
\ifproof\global\advance\nc1
        \let\aa#1\let\bb#2\fi
 \global\status0 \continuetrue
 {\loop\ifx\empty#1\continuefalse\fi
       \ifx\empty#2\continuefalse\fi
  \ifcontinue\nxt#1\nxtt\nxt#2\nxtu
             \lge\nxtt\nxtu
  \repeat}\ifnum0=\status
 \ifx\empty#1\ifx\empty#2\else
                  \global\status2 \fi
 \else\ifx\empty#2\global\status1 \fi
 \fi\fi
 \ifproof\immediate\write16{\aa
  \ifnum0=\status=\else
   \ifnum1=\status>\else
                  <\fi\fi\bb.}
 \fi%end ifproof
}
%
\def\lge#1#2{%#1 and #2 letter values
%Result: \status= 0, 1, 2, if
%              #1 =, >, <  #2.
%and \continuefalse if #1=/#2.
 \ifnum#1=#2{}\else\continuefalse
  \ifnum#1<#2\global\status2 \else
             \global\status1 \fi
 \fi}
%
\def\nxtw#1#2{\def\pop##1##2\pop{%
 \gdef#1{##2}\def\head{##1}}%head and tail
 \ea\pop#1\pop%split in head and tail
 \ea\loc\head\accstr%\head is an accent cs?
 \iffound\let\acs\head
  \ea\pop#1\pop%next head and tail
  \ea\let\ea#2\csname ot\acs\head\endcsname
 \else\ea\let\ea#2\csname ot\head\endcsname
 \fi}
%
\def\loc#1#2{\def\locate##1#1##2\end
 {\ifx\empty##2\empty\foundfalse
 \else\foundtrue\fi}\ea\locate#2.#1\end}
%
%Parameters:  for ASCII words
\def\nxtaw#1#2{%Result: value of first
%letter of string supplied in #1 is delivered
%in #2. (To be used as a number (\chardef)).
%#1, #2 are control sequences.
 \def\pop##1##2\pop{\gdef#1{##2}%
  \chardef#2=`##1{}}\ea\pop#1\pop}
%
\def\cmpir#1#2{%#1, #2 defs
%Result: \status= 0, 1, 2 if
%        \val{#1} =, >, < \val{#2}
 \ea\ea\ea\decom\ea#1\ea;#2.}
%
\def\decom#1 !#2 #3;#4 !#5 #6.{%
 \def\one{#1}\def\four{#4}\cmpaw\one\four
 \ifnum0=\status%Compare secondary keys
   \ifnum#2<#5{}\global\status2{}\else
     \ifnum#2>#5{}\global\status1{}\else
                %Compare tertiary keys
       \ifnum#3<#6{}\global\status2{}\else
         \ifnum#3>#6{}\global\status1{}\fi
       \fi
     \fi
   \fi
 \fi}
%
\def\red{%Reduction of \1,...,\n
 \k0\kk0\let\refer\empty
 \loop\ifnum\k<\n\advance\k1
  \ea\let\ea\record\csname\the\k\endcsname
  \ea\splitwn\record.%
  \ifx\refer\word%extend with number
    \ea\xdef\csname\the\kk\endcsname{%
       \csname\the\kk\endcsname, \num}%
  \else%write record to \kk
   \advance\kk1\let\refer\word\ea\global
   \ea\let\csname\the\kk\endcsname\record
  \fi
 \repeat\n=\kk}
%
\def\redrng{%Reduction of \1,...,\n, with
%range representation of page numbers
 {\k1\kk0
 \ea\let\ea\record\csname\the\k\endcsname
 \ea\splitwn\record.\let\refer\word
 \let\nrs\empty\prcrng\num
 \loop\ifnum\k<\n\advance\k1
  \ea\let\ea\record\csname\the\k\endcsname
  \ea\splitwn\record.%
  \ifx\refer\word%extend \nrs with number
    \prcrng\num
  \else%write record to \kk
    \advance\kk1 \strnrs
    \ea\xdef\csname\the\kk\endcsname{\refer{}
      \nrs}\let\nrs\empty\init\num\prcrng\num
    \let\refer\word
  \fi
 \repeat\ifnum1<\n
  \advance\kk1 \strnrs
  \ea\xdef\csname\the\kk\endcsname{\word{}
    \nrs}
 \global\n\kk\fi}}
%
\def\prcrng#1{\init{#1}\def\prcrng##1{%
 \ifnum##1=\lst\else\ifnum##1=\slst
  \lst\slst\advance\slst1 \else
  \strnrs\init{##1}\fi\fi}}
%
\def\strnrs{\dif\lst\advance\dif-\frst
 \edef\nrs{\ifx\nrs\empty\else\nrs\sepn\fi
  \the\frst\ifnum0<\dif
   \ifnum1=\dif\sepn\the\lst
   \else\nobreak--\nobreak\the\lst
   \fi
  \fi}}
%
\def\splitwn#1 !#2 #3.{\def\word{#1 !#2}%
 \def\num{#3}}
%
\def\getdig#1 !#2 #3.{\def\dig{#2}}
%
\def\sortcs{\global\k0\global\pk\n
\global\pkone\pk\global\advance\pkone1
%Invariant: 1:k non-cs; pk+1:n control seq-s
\loop\global\advance\k1
\ifnum\k<\pkone
 \ea\ea\ea\getdig\csname\the\k\endcsname.%
 \if2\dig{\continuetrue
  \loop
   \ifnum\k=\pk\continuefalse
   \else\ea\ea\ea\getdig\csname\the\pk
                          \endcsname.%
    \if2\dig
    \else\xch\k\pk\continuefalse
    \fi
   \fi\global\pkone\pk\global\advance\pk-1
  \ifcontinue
  \repeat}%
 \fi
\repeat}%Result\1:\pk non-cs, \pkone:\n cs
%
%Parameters: Ordering table
\chardef\ota=32 \chardef\otA=32
 \chardef\otaa=33 \chardef\otag=33
 \chardef\otat=34 \chardef\otah=35
\chardef\otb=39 \chardef\otB=39
\chardef\otc=46 \chardef\otC=46
 \chardef\otcc=47 \chardef\otcc=47
\chardef\otd=53 \chardef\otD=53
\chardef\ote=60 \chardef\otE=60
 \chardef\otea=61 \chardef\oteg=62
 \chardef\otet=63 \chardef\oteh=64
\chardef\otf=67 \chardef\otF=67
\chardef\otg=74 \chardef\otG=74
\chardef\oth=81 \chardef\otH=81
\chardef\oti=88 \chardef\otI=88
 \chardef\otit=91 \chardef\otih=92
\chardef\otj=95 \chardef\otJ=95
 \chardef\otjt=98
\chardef\otk=102 \chardef\otK=102
\chardef\otl=109 \chardef\otL=109
\chardef\otm=116 \chardef\otM=116
\chardef\otn=123 \chardef\otN=123
\chardef\oto=130 \chardef\otO=130
 \chardef\otoa=131 \chardef\otog=132
 \chardef\otot=133 \chardef\otoh=134
\chardef\otp=137 \chardef\otP=137
\chardef\otq=143 \chardef\otQ=143
\chardef\otr=150 \chardef\otR=150
\chardef\ots=157 \chardef\otS=157
\chardef\ott=164 \chardef\otT=164
\chardef\otu=171 \chardef\otU=171
 \chardef\otut=174 \chardef\otuh=175
\chardef\otv=178 \chardef\otV=178
\chardef\otw=185 \chardef\otW=185
\chardef\otx=192 \chardef\otX=192
\chardef\otij=199 \chardef\otIJ=199
\chardef\oty=200 \chardef\otY=200
\chardef\otz=206 \chardef\otZ=206
%\endinput                   %cgl@rug.nl
%
%%%%%%%%%% heap sort macro      %%%%%%%%%%
%heapsort.tex                    Jan, 93
\newcount\n\newcount\lc\newcount\r
\newcount\ic\newcount\uone
\newcount\jc\newcount\jj\newcount\jjone
\newif\ifgoon
%Non-descending sorting
\def\heapsort{%data in \1 to \n
\r=\n\heap\ic=1{}%
{\loop\ifnum\r>1{}\xch\ic\r
   \advance\r-1{}\sift\ic\r
\repeat}}
%
\def\heap{%Transform \1..\n into heap
 \lc=\n\divide\lc2{}\advance\lc1{}%
 {\loop\ifnum\lc>1{}\advance\lc-1{}%
  \sift\lc\n\repeat}}
%
\def\sift#1#2{%#1, #2 counter variables
 \jj=#1\uone=#2\advance\uone1{}\goontrue
 {\loop\jc=\jj \advance\jj by\jj
  \ifnum\jj<\uone
   \jjone=\jj \advance\jjone1{}%
   \ifnum\jj<#2{}\cmpval\jj\jjone
         \ifnum2=\status\jj=\jjone\fi\fi
   \cmpval\jc\jj\ifnum2>\status\goonfalse\fi
 \else\goonfalse\fi
\ifgoon\xch\jc\jj\repeat}}
%
\def\cmpval#1#2{%#1, #2 counter variables
%Result: \status= 0, 1, 2 if
%        \val{#1} =, >, < \val{#2}
 \ea\let\ea\aone\csname\the#1\endcsname
 \ea\let\ea\atwo\csname\the#2\endcsname
 \cmp\aone\atwo}
%\endinput                    %cgl@rug.nl
%
%%%%%%%%%% quick sort macro      %%%%%%%%%%
\newcount\low\newcount\up\newcount\m
\def\quicksort{%Values given in
%\low,...,\up are sorted, non-descending.
%Parameters: \cmp, comparison.
 \ifnum\low<\up\else\brk\fi
%\refval, a reference value selected at random.
 \m=\up\advance\m-\low%Size-1 of array part
 \ifnum10<\m\rnd\multiply\m\rndval
   \divide\m99{}\advance\m\low \xch\low\m
 \fi
 \ea\let\ea\refval\csname\the\low\endcsname
 \m=\low\k=\low\let\refvalcop=\refval
 {\loop\ifnum\k<\up\advance\k1{}%
   \ea\let\ea\oneqs\csname\the\k\endcsname
   \cmp\refval\oneqs\ifnum1=\status
      \global\advance\m1{}\xch\m\k\fi
   \let\refval=\refvalcop
  \repeat}\xch\low\m
 {\up=\m\advance\up-1{}\quicksort}%
 {\low=\m\advance\low1{}\quicksort}\krb}
%
\def\brk#1\krb{\fi}\def\krb{\relax}
%\endinput                      %cgl@rug.nl
%
%%%%%%%%%% Example: heap sort   %%%%%%%%%%
\onecolumn
\section{Appendix: Heap Sort}                     %Aug, 93, cgl@risc1.rug.nl
The process consists of two main steps:
 creation of a heap, and sorting the heap.
A sift operation is used in both.

In comparison with my earlier release of the code in MAPS92.2,
I adapted the notation with respect to sorting in {\em non-decreasing\/}
order.\ftn{It is true that the reverse of the comparison operation would
   do, but it seemed more consistent to me to adapt
   the notation of the heap concept with
   the smallest elements at the bottom.}

What is a heap? A sequence $a_1, a_2, \ldots, a_n$, is a heap if
$a_k\ge a_{2k} \wedge a_k\ge a_{2k+1}, k=1, 2, \ldots, n\div2$, and
because $a_{n+1}$ is undefined, the notation is simplified by
defining  $a_k>a_{n+1}, k= 1, 2, \ldots , n$.
\\
For example, a tree and one of its heap representations of $2, 6, 7, 1, 3, 4$
read
$$\setlength{\unitlength}{3ex}
\vcenter{\noindent\hsize=18ex
\begin{picture}(7,4.5)(0,-.5)
\put(.5,.5){\circle{1}}
\put(.5,.5){\makebox(0,0){1}}
\put(2.5,.5){\circle{1}}
\put(2.5,.5){\makebox(0,0){3}}
\put(4.5,.5){\circle{1}}
\put(4.5,.5){\makebox(0,0){4}}
\put(1.5,2.5){\circle{1}}
\put(1.5,2.5){\makebox(0,0){6}}
\put(5.5,2.5){\circle{1}}
\put(5.5,2.5){\makebox(0,0){7}}
\put(3.5,3.5){\circle{1}}
\put(3.5,3.5){\makebox(0,0){2}}
\put(.9,1){\line(1,2){.5}}
\put(2.1,1){\line(-1,2){.5}}
\put(4.9,1){\line(1,2){.5}}
\put(2,2.9){\line(2,1){1}}
\put(5,2.9){\line(-2,1){1}}
\end{picture}}
\qquad\qquad
\vcenter{\noindent\hsize=21ex
\begin{picture}(7,5)(0,-.5)
\put(.5,.5){\circle{1}}
\put(.5,.5){\makebox(0,0){2}}
\put(2.5,.5){\circle{1}}
\put(2.5,.5){\makebox(0,0){3}}
\put(4.5,.5){\circle{1}}
\put(4.5,.5){\makebox(0,0){1}}
\put(1.5,2.5){\circle{1}}
\put(1.5,2.5){\makebox(0,0){6}}
\put(5.5,2.5){\circle{1}}
\put(5.5,2.5){\makebox(0,0){4}}
\put(3.5,3.5){\circle{1}}
\put(3.5,3.5){\makebox(0,0){7}}
\put(.9,1){\line(1,2){.5}}
\put(2.1,1){\line(-1,2){.5}}
\put(4.9,1){\line(1,2){.5}}
\put(2,2.9){\line(2,1){1}}
\put(5,2.9){\line(-2,1){1}}
\end{picture}}
$$
%
\subsection{The algorithm.}
In a pseudo notation the algorithm,
for sorting the array a[1:n], reads

\def\PO#1{\mathop{\hbox{\bf#1}}}
\def\P#1{\hbox{\bf#1}\,}
{\obeylines \parindent=0pt
\%heap creation
$l:=n\PO{div}2+1;          $
$\P{while} l\ne1 \PO{do} l:=l-1; sift(a, l, n)\PO{od}$
\%sorting
$r:=n;                      $
$\P{while} r\ne1 \PO{do} (a[1], a[r]):=(a[r], a[1])\%exchange $
$\quad r:=r-1; sift(a, 1, r)\PO{od} $
\%sift \#1 through \#2
$j:=\#1                     $
$\P{while} 2j\geq\#2 \wedge(a[j]<a[2j]\vee a[j]<a[2j+1])\PO{do} $
$\quad mi:=2j+\PO{if}a[2j]>a[2j+1]\PO{then}0\PO{else}1\PO{fi}$
$\quad exchange(a[j], a[mi])\,j:=mi\,\P{od}$
}%end scope \obeylines
%
\subsection{Encoding: Purpose.} Sorting values given in an array.
%
\subsection{Encoding: Input.} The values are stored in the control sequences
\verb|\1|, \ldots, \verb|\|$\langle n\rangle$.
The counter \verb|\n| must contain the value $\langle n\rangle$.
The parameter for comparison, \verb|\cmp|,
must be \verb|\let|-equal to \verb|\cmpn|, for numerical
comparison, to \verb|\cmpw|, for word comparison, to \verb|\cmpaw|,
for word comparison obeying the ASCII ordering, or to a comparison
macro of your own.
(The latter macro variants, and in general the common definitions for
 \verb|\heapsort|, and \verb|\quicksort|,
 are supplied in the file \verb|sort.tex|, see van der Laan (1993).)
%
\subsection{Encoding: Output.}
The sorted array \verb|\1|, \verb|\2|, \ldots \verb|\|$\langle n\rangle$,
with  \verb|\val1| $\le$ \verb|\val2| $\le$
\ldots $\le$ \verb|\val|$\langle n\rangle$. %\ftn{And {\tt\char92%
   %def\char92val\#1$\{$\char92csname\#1\char92endcsname$\}$.}}
%
\subsection{Encoding: Source.}
\begin{verbatim}
%heapsort.tex                    Jan, 93
\newcount\n\newcount\lc\newcount\r\newcount\ic\newcount\uone
\newcount\jc\newcount\jj\newcount\jjone       \newif\ifgoon
%Non-descending sorting
\def\heapsort{%data in \1 to \n
\r\n\heap\ic1
{\loop\ifnum1<\r \xch\ic\r \advance\r-1 \sift\ic\r\repeat}}
%
\def\heap{%Transform \1..\n into heap
 \lc\n\divide\lc2{}\advance\lc1
 {\loop\ifnum1<\lc\advance\lc-1 \sift\lc\n\repeat}}
%
\def\sift#1#2{%#1, #2 counter variables
 \jj#1\uone#2\advance\uone1 \goontrue
 {\loop\jc\jj \advance\jj\jj
  \ifnum\jj<\uone \jjone\jj \advance\jjone1
    \ifnum\jj<#2 \cmpval\jj\jjone
         \ifnum2=\status\jj\jjone\fi
    \fi\cmpval\jc\jj\ifnum2>\status\goonfalse\fi
  \else\goonfalse
  \fi
  \ifgoon\xch\jc\jj\repeat}}
%
\def\cmpval#1#2{%#1, #2 counter variables
%Result: \status= 0, 1, 2 if
%values pointed by
%              #1 =, >, < #2
 \ea\let\ea\aone\csname\the#1\endcsname
 \ea\let\ea\atwo\csname\the#2\endcsname
 \cmp\aone\atwo}
\endinput                    %cgl@risc1.rug.nl
\end{verbatim}
%
\subsection{Explanation: {\tt\char92heapsort}.}
The values given in \verb|\1,...\|$\langle n\rangle$,
are sorted in non-descending order.
\subsection{Explanation: {\tt\char92heap}.}
The values given in \verb|\1|, \ldots, \verb|\|$\langle n\rangle$,
 are rearranged into a heap.
\subsection{Explanation: {\tt\char92sift}.}
The first element denoted by the first (counter) argument
has disturbed the heap. Sift rearranges
the part of the array denoted by its two arguments, such that the
heap property holds again.
\subsection{Explanation: {\tt\char92cmpval}.}
The values denoted by the counter values,
  supplied as arguments, are compared.
%
\subsection{Examples of use: Numbers, words.} %, and accented words)
After \verb=\input heap \input sort=
\begin{verbatim}
\def\1{314}\def\2{1}\def\3{27}\n3 \let\cmp\cmpn\heapsort
\begin{quote}\prtn,\end{quote}
%
\def\1{ab}\def\2{c}\def\3{aa}\n3  \let\cmp\cmpaw\heapsort
\begin{quote}\prtw,\end{quote}
and
\def\1{j\ij}\def\2{ge\"urm}\def\3{gar\c con}\def\4{\'el\`eve}\n4
\let\cmp\cmpw {\accdef\heapsort}
\begin{quote}\prtw\end{quote}
\end{verbatim}
yields\ftn{{\tt\char92accdef} suitably redefines the
   accents within this scope.}
\def\1{314}\def\2{1}\def\3{27}\n=3
{\let\cmp\cmpn\heapsort
\begin{quote}\prtn,\end{quote}
%
\def\1{ab}\def\2{c}\def\3{aa}\n=3
\let\cmp\cmpaw\heapsort
\begin{quote}\prtw,\end{quote}
and
\def\1{j\ij}\def\2{ge\"urm}\def\3{gar\c con}\def\4{\'el\`eve}\n=4
\let\cmp=\cmpw{\accdef\heapsort}
\begin{quote}\prtw.\end{quote}
}
%
\clearpage
%%%%%%%%%% Example: quick sort  %%%%%%%%%%
\section{Appendix: Quick Sort}
The quick sort algorithm has been discussed in many places. %,
%for example \cite{dek73}.
Here the following code due to Bentley    %\cite{jb86}, p.~112,
has been transliterated.\footnote{L, U have been changed in the \TeX\ code
   into low, up.}
\begin{verbatim}
procedure QSort(L,U)
if L<U then Swap(X[l], X[RandInt(L,U)]) T:=X[L] M:=L
   for I:=L+1 to U do if X[I]<T M:=M+1 Swap(X[M], X[I]) fi od
   Swap(X[L], X[M])
   QSort(L, M-1) QSort(M+1, U)
fi
\end{verbatim}
%
\subsection{Encoding: Purpose.}
Sorting of the values given in the array
\verb|\|$\langle low\rangle$, \ldots, \verb|\|$\langle up\rangle$.
\subsection{Encoding: Input.}
The values are stored in
\verb|\|$\langle low\rangle$, \ldots, \verb|\|$\langle up\rangle$,
with $1\le low\le up\le n$.
The parameter for comparison, \verb|\cmp|,
must be \verb|\let|-equal
to \verb|\cmpn|, for number comparison,
to \verb|\cmpw|, for word comparison,
to \verb|\cmpaw|,
for word comparison obeying the ASCII ordering,
or to a comparison macro of your own.
(The latter macros, and in general the common definitions for
 \verb|\heapsort|, and \verb|\quicksort|,
 are supplied in the file \verb|sort.tex|, see van der Laan (1993).)
%
\subsection{Encoding: Output.}
The sorted array \verb|\|$\langle low\rangle$,
\ldots \verb|\|$\langle up\rangle$, with
\verb|\val|$\langle low\rangle \le
\dots \le{}$ \verb|\val|$\langle up\rangle$.
%
\subsection{Encoding: Source.}
\begin{verbatim}
%quick.tex                        Jan 93
\newcount\low\newcount\up\newcount\m
\def\quicksort{%Values given in \low,...,\up are sorted, non-descending.
%Parameters: \cmp, comparison.
 \ifnum\low<\up\else\brk\fi
%\refval, a reference value selected at random.
 \m\up\advance\m-\low%Size-1 of array part
 \ifnum10<\m\rnd\multiply\m\rndval
   \divide\m99 \advance\m\low \xch\low\m
 \fi
 \ea\let\ea\refval\csname\the\low\endcsname
 \m\low\k\low\let\refvalcop\refval
 {\loop\ifnum\k<\up\advance\k1
   \ea\let\ea\oneqs\csname\the\k\endcsname
   \cmp\refval\oneqs\ifnum1=\status\global\advance\m1 \xch\m\k\fi
   \let\refval\refvalcop
  \repeat}\xch\low\m
 {\up\m\advance\up-1 \quicksort}{\low\m\advance\low1 \quicksort}\krb}
%
\def\brk#1\krb{\fi}\def\krb{\relax}
\endinput                      %cgl@risc1.rug.nl
\end{verbatim}
\subsection{Explanation.}
At each level the array is partitioned into two parts.
After partitioning
the left part contains values less than the reference value and the
right part contains values greater than or equal to the reference value.
Each part is again partitioned via a recursive call of the macro.
The array is sorted when all parts are partitioned.

In the \TeX\ encoding
the reference value as estimate for the mean value is determined
via a random selection of one of the elements.
The random number is mapped into
the range [$\,low:up\,$], via the linear transformation
$\hbox{\tt\char92low}+(\hbox{\tt\char92up}-\hbox{\tt\char92low})*
\hbox{\tt\char92rndval}/99$.\ftn{Note that the number is guaranteed within
   the range.}

The termination of the recursion is  encoded in
a \TeX\ peculiar way.
First, I encoded the infinite loop. Then  I inserted
the condition for termination with the \verb|\fi| on the same line,
and not enclosing the main part of the macro.
On termination the invocation \verb|\brk|
gobbles up all the tokens
at that level up to its separator \verb|\krb|,
and inserts its replacement text\Dash a new \verb|\fi|\Dash %
to compensate for the gobbled \verb|\fi|.
%
\subsection{Examples: Numbers, words.}
After \verb=\input quick \input sort=
\begin{verbatim}
\def\1{314}\def\2{1}\def\3{27}\n3 \low1\up\n\let\cmp\cmpn
\quicksort
\begin{quote}\prtn,\end{quote}
%
\def\1{ab}\def\2{c}\def\3{aa}\def\4{\ij}\def\5{ik}\def\6{z}\def\7{a}\n7
\low1\up\n\let\cmp\cmpw \quicksort
\begin{quote}\prtw,\end{quote}
and
\def\1{j\ij}\def\2{ge\"urm}\def\3{gar\c con}\def\4{\'el\`eve}\n4
\low1\up\n\let\cmp\cmpw  {\accdef\quicksort}
\begin{quote}\prtw.\end{quote}
\end{verbatim}
yields\ftn{{\tt\char92accdef} suitably redefines the
   accents within this scope.}
\def\1{314}\def\2{1}\def\3{27}\n3
{\low1\up\n\let\cmp\cmpn  \quicksort
\begin{quote}\prtn,\end{quote}
%
\def\1{ab}\def\2{c}\def\3{aa}
\def\4{\ij}\def\5{ik}\def\6{z}\def\7{a}\n7
\low1\up\n\let\cmp\cmpw  \quicksort
\begin{quote}\prtw,\end{quote}
and
\def\1{j\ij}\def\2{ge\"urm}\def\3{gar\c con}
\def\4{\'el\`eve}\n=4
\low=1\up=\n\let\cmp=\cmpw
{\accdef\quicksort}
\begin{quote}\prtw.\end{quote}
}
%end appendices
\end{document}