diff options
author | Norbert Preining <norbert@preining.info> | 2019-09-02 13:46:59 +0900 |
---|---|---|
committer | Norbert Preining <norbert@preining.info> | 2019-09-02 13:46:59 +0900 |
commit | e0c6872cf40896c7be36b11dcc744620f10adf1d (patch) | |
tree | 60335e10d2f4354b0674ec22d7b53f0f8abee672 /macros/generic/laansort/sort.tex |
Initial commit
Diffstat (limited to 'macros/generic/laansort/sort.tex')
-rw-r--r-- | macros/generic/laansort/sort.tex | 796 |
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} |