summaryrefslogtreecommitdiff
path: root/macros/generic/laansort
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
committerNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
commite0c6872cf40896c7be36b11dcc744620f10adf1d (patch)
tree60335e10d2f4354b0674ec22d7b53f0f8abee672 /macros/generic/laansort
Initial commit
Diffstat (limited to 'macros/generic/laansort')
-rw-r--r--macros/generic/laansort/sort.tex796
1 files changed, 796 insertions, 0 deletions
diff --git a/macros/generic/laansort/sort.tex b/macros/generic/laansort/sort.tex
new file mode 100644
index 0000000000..c6b9214da9
--- /dev/null
+++ b/macros/generic/laansort/sort.tex
@@ -0,0 +1,796 @@
+
+%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}