| 1 |
% \iffalse meta-comment |
| 2 |
% |
| 3 |
% Copyright (C) 2019 by Laurence R Taylor |
| 4 |
% ----------------------------------- |
| 5 |
% |
| 6 |
% This file may be distributed and/or modified under the |
| 7 |
% conditions of the LaTeX Project Public License, either version 1.3c |
| 8 |
% of this license or (at your option) any later version. |
| 9 |
% The latest version of this license is in: |
| 10 |
% |
| 11 |
% http://www.latex-project.org/lppl.txt |
| 12 |
% |
| 13 |
% and version 1.3c or later is part of all distributions of LaTeX |
| 14 |
% version 2005/12/01 or later. |
| 15 |
% |
| 16 |
% \fi |
| 17 |
% |
| 18 |
% \iffalse |
| 19 |
% |
| 20 |
%<*driver> |
| 21 |
\documentclass{ltxdoc} |
| 22 |
\usepackage{bubblesort} |
| 23 |
\usepackage{graphicx} |
| 24 |
\usepackage{hyperref} |
| 25 |
\hypersetup{ |
| 26 |
colorlinks=true, |
| 27 |
linkcolor=blue, |
| 28 |
filecolor=magenta, |
| 29 |
urlcolor=cyan, |
| 30 |
} |
| 31 |
\DisableCrossrefs |
| 32 |
\CodelineNumbered |
| 33 |
\RecordChanges |
| 34 |
\begin{document} |
| 35 |
\DocInput{bubblesort.dtx} |
| 36 |
\end{document} |
| 37 |
%</driver> |
| 38 |
% \fi |
| 39 |
% |
| 40 |
% \CheckSum{293} |
| 41 |
% |
| 42 |
% \CharacterTable |
| 43 |
% {Upper-case \A\B\C\D\E\F\G\H\I\J\K\L\M\N\O\P\Q\R\S\T\U\V\W\X\Y\Z |
| 44 |
% Lower-case \a\b\c\d\e\f\g\h\i\j\k\l\m\n\o\p\q\r\s\t\u\v\w\x\y\z |
| 45 |
% Digits \0\1\2\3\4\5\6\7\8\9 |
| 46 |
% Exclamation \! Double quote \" Hash (number) \# |
| 47 |
% Dollar \$ Percent \% Ampersand \& |
| 48 |
% Acute accent \' Left paren \( Right paren \) |
| 49 |
% Asterisk \* Plus \+ Comma \, |
| 50 |
% Minus \- Point \. Solidus \/ |
| 51 |
% Colon \: Semicolon \; Less than \< |
| 52 |
% Equals \= Greater than \> Question mark \? |
| 53 |
% Commercial at \@ Left bracket \[ Backslash \\ |
| 54 |
% Right bracket \] Circumflex \^ Underscore \_ |
| 55 |
% Grave accent \` Left brace \{ Vertical bar \| |
| 56 |
% Right brace \} Tilde \~} |
| 57 |
% |
| 58 |
% |
| 59 |
% \hfuzz=200pt |
| 60 |
% \changes{v1.0}{?2019?/?07?/?17?}{Initial version} |
| 61 |
% \title{bubblesort} |
| 62 |
% \author{Laurence R Taylor} |
| 63 |
% \date{2020/06/24} |
| 64 |
% \maketitle |
| 65 |
% \begin{abstract} |
| 66 |
% This package is a \LaTeX\ port of the sorting function \href{https://en.wikipedia.org/wiki/Bubble_sort}{bubble sort}. |
| 67 |
% Bubble sort is usually coded using arrays but it can be done without them and |
| 68 |
% since \LaTeX\ does not support arrays natively, bubble sort seemed like a good routine to port. |
| 69 |
% It's lack of speed is not really a problem with the data sizes likely to be encountered in most \LaTeX\ applications. |
| 70 |
% |
| 71 |
% The objects to be sorted are either a stack or a list. |
| 72 |
% A \emph{stack} is a sequence of legal \TeX\ code items enclosed in brace pairs, \vskip0pt% |
| 73 |
% \begin{center}|{|\emph{item 1}|}{|\emph{item 2}|}|\dots|{|\emph{item n}|}|\end{center} |
| 74 |
% while a \emph{list} is a macro which expands to a stack. Fragile commands in an \emph{item} may not work as expected. |
| 75 |
% To sort the items one needs a notion of when one \emph{item} is ``less than'' another. |
| 76 |
% |
| 77 |
% The macro |\bubblesort| does the bubble sort. It takes three arguments: |\bubblesort[#1]{#2}{#3}|. |
| 78 |
% The optional argument is a comparator macro telling when one item is smaller than another. |
| 79 |
% If empty it assumes the stack is a stack of integers or real numbers |
| 80 |
% and sorts it using the usual $<$. Argument |#2| is the stack or list to be sorted and |
| 81 |
% argument |#3| a macro which will contain the sorted list in increasing order. |
| 82 |
% |
| 83 |
% The only dependency is |etoolbox.sty|. |
| 84 |
% \end{abstract} |
| 85 |
% \section{Introduction} |
| 86 |
% \makeatletter |
| 87 |
% \newcounter{LineAA} |
| 88 |
% \def\Label#1{\hypertarget{@bubblesort@ref#1}\relax\setcounter{LineAA}{\value{CodelineNo}}\stepcounter{LineAA} |
| 89 |
% {\immediate\write\@auxout{\string\gdef\string\@bubblesort@ref#1{\number\value{LineAA}}}}} |
| 90 |
% \def\codeRef#1{\ifcsdef{@bubblesort@ref#1}{\hyperlink{@bubblesort@ref#1}{\csname @bubblesort@ref#1\endcsname}}{\textbf{??}}} |
| 91 |
% \def\LabelLine#1{\Label{#1}\nointerlineskip\begin{macrocode}} |
| 92 |
% \newbox\ff\setbox\ff=\hbox{\scalebox{0.75}{\hbox{\Large\tt doublebubblesort}}} |
| 93 |
% \newbox\fff\setbox\fff=\hbox{\scalebox{0.75}{\hbox{\Large\tt doublebubblesortB}}} |
| 94 |
% \newbox\mm\setbox\mm=\hbox{\rotatebox{114}{\vrule depth0.8pt height 0pt width 9pt}} |
| 95 |
% \makeatother |
| 96 |
% \newbox\ff\setbox\ff=\hbox{\scalebox{0.75}{\hbox{\Large\tt doublebubblesort}}} |
| 97 |
% \newbox\fff\setbox\fff=\hbox{\scalebox{0.75}{\hbox{\Large\tt doublebubblesortB}}} |
| 98 |
% \newbox\mm\setbox\mm=\hbox{\rotatebox{114}{\vrule depth0.8pt height 0pt width 9pt}} |
| 99 |
% There are two macros provided which implement the standard bubble sort algorithms |
| 100 |
% on stacks or lists. See section \ref{SandL} for a discussion of stacks or lists. |
| 101 |
% \subsection{\texorpdfstring{\copy\mm\tt bubblesort}{bubblesort}} |
| 102 |
% |\bubblesort[#1]{#2}{#3}|: Argument |#2| is the stack or list to be sorted. Argument |#3| contains the sorted list |
| 103 |
% after evaluation. Argument |#2| can be the same as argument |#3|. Argument |#3| can also be blank in which |
| 104 |
% case the output string is inserted into the input stream. |
| 105 |
% Optional argument |#1| is a comparator macro. |
| 106 |
% \subsubsection{Comparator macros} |
| 107 |
% A comparator macro can have any legal \TeX\ name. It must have two arguments. |
| 108 |
% When in use the comparator macro is evaluated on consecutive pairs of elements in the stack. |
| 109 |
% If argument |#2| is ``smaller'' than argument |#1| the macro sets |\bubblesortflag| to |1| and sets it |
| 110 |
% to |-1| otherwise. |
| 111 |
% Two examples are supplied: |\realSort| on line \codeRef{realSort}\ of the code below and |
| 112 |
% |\alphSort| on line \codeRef{alphSort}. |
| 113 |
% |
| 114 |
% \subsection{\texorpdfstring{\copy\mm\tt doublebubblesort}{bubblesort}}|\doublebubblesort[#1]{#2}{#3}{#4}{#5}|: |
| 115 |
% |
| 116 |
% The macro |\doublebubblesort| sorts two stack/lists. Arguments |#1|, |#2| and |#3| are identical to the corresponding |
| 117 |
% arguments for |\bubblesort|. Argument |#4| is another stack or list of the same length or longer than stack/list |#2|. |
| 118 |
% When expanded |\doublebubblesort| sorts |#2| just the same as |\bubblesort| would. However, every move made on |
| 119 |
% stack |#2| is also done on stack |#4|. Argument |#5| is the name for the output of the result of this ``sort'' on |#4|. |
| 120 |
% As usual |#5| can be blank or |#4| and |#5| can be the same macro. |#3| and |#5| can also be the same macro, in |
| 121 |
% which case it contains the result of the sort on argument |#4|, \emph{except} if both |#3| and |#5| are blank, |#3| |
| 122 |
% is put into the input stream followed by |#5|. |
| 123 |
% |
| 124 |
% An example to keep in mind is the following. One way to mimic a hash in \LaTeX\ is to have a list of keys and a second |
| 125 |
% list of values with the value associated to a key being determined by position in the values list. If the key list is sorted it |
| 126 |
% will be necessary to do the same interchanges on the values list to maintain the correspondence. |
| 127 |
% See subsection \ref{permute} for another example using |\doublebubblsort|. |
| 128 |
% \section{Stacks and lists}\label{SandL} |
| 129 |
% The lists here closely resemble Knuth's lists in the |
| 130 |
% \href{http://www.ctex.org/documents/shredder/src/texbook.pdf}{\TeX book}, page 378, Appendix D, |
| 131 |
% except they lack Knuth's initial |\\| prepended to each item. As discussed by Knuth, the |\\| can be used to process |
| 132 |
% each item in the list. |
| 133 |
% Sort algorithms require knowledge of pairs of items from the list |
| 134 |
% so macros which only know about one item are not needed. |
| 135 |
% |
| 136 |
% |
| 137 |
% Other implementations of lists use a reserved character as a separator. |
| 138 |
% Separators like commas or semicolons or whatever have the drawback that then the separator can not be used in the item text |
| 139 |
% without additional coding. |
| 140 |
% |
| 141 |
% \TeX's brace-pair mechanism is quite robust. It handles nested brace pairs just fine. One word of \textcolor{red}{warning}: |
| 142 |
% an empty brace pair |{}| is used as an end of list indicator. They are added to the stack/list arguments |
| 143 |
% when needed and are not present at the end of lists produced by macros in this package so they rarely trouble the user. |
| 144 |
% It does mean that |
| 145 |
% \textcolor{red}{there can be no empty (or even |{white space}|) brace pairs in the input list.} |
| 146 |
% Given how \TeX\ discards white space, |{white space}| is probably not what is wanted anyway. Using |{{white space}}| will probably |
| 147 |
% yield results closer to what was intended and this works. |
| 148 |
% \section{Examples} |
| 149 |
% Here are a few examples if things that can be done with sorts. |
| 150 |
% \subsection{\texorpdfstring{\copy\mm\tt refs}{refs}} |
| 151 |
% Given a stack of references defined from |\label| such as |{ref 1}{ref 2}|\dots|{ref n}| which expand to integers or real numbers |
| 152 |
% try to define |
| 153 |
% \begin{center} |
| 154 |
% \color{red}|\def\refs#1{\bubblesort[\refSort]{#1}{\answers}}|\hskip1in\null \\where |\refSort#1#2{\realSort{\ref{#1}}{\ref{#2}}}|. \color{black} |
| 155 |
% \end{center} |
| 156 |
% The above does not work because |\ref| is protected and does not expand to just the number. |
| 157 |
% Instead, the package |refcount.sty| supplies |\getrefnumber| which is expandable and does what is needed. |
| 158 |
% Add |\usepackage{refcount}| to the preamble and define |
| 159 |
% \begin{verbatim} |
| 160 |
% \def\refSort#1#2{% |
| 161 |
% \edef\aa{\getrefnumber{#1} pt}\edef\bb{\getrefnumber{#2} pt}% |
| 162 |
% \ifdimless{\bb}{\aa}{\bubblesortflag=1}{\bubblesortflag=-1}% |
| 163 |
% } |
| 164 |
% \end{verbatim} |
| 165 |
% Then|\def\refs#1{\bubblesort[\refSort]{#1}{\ans}}| sorts the numbers in increasing order and puts the answer in |\ans|. |
| 166 |
% |
| 167 |
% \subsection{Use {\texorpdfstring{\copy\mm\tt refs}{refs}}\ twice} |
| 168 |
% Since |\bubblesort| is a stable sorting algorithm, it can be usefully used more than once on the same data. |
| 169 |
% Suppose |\refSort| is defined as above and there is a list |\def\LL{{ref 1}{ref 2}|\dots|{ref n}}|. |
| 170 |
% Then |\bubblesort[\refSort]{\LL}{\LL}| sorts the numbers in increasing order. |
| 171 |
% |
| 172 |
% But some of them may be from definitions, others from theorems, or lemmas, etc. |
| 173 |
% Suppose |\refName#1| is a macro such that |\refName{ref k}| returns |Definition|, |Theorem|, |Lemma|, etc.. |
| 174 |
% Then |
| 175 |
% \begin{center} |
| 176 |
% |\bubblesort[\refSort]{\LL}{\LL} \bubblesort[\alphSort]{\LL}{\LL}| |
| 177 |
% \end{center} |
| 178 |
% \noindent returns |
| 179 |
% |\def\LL{{ref k_1}{ref k_2}|\dots|{ref k_n}}| |
| 180 |
% where the first set of references are |Definition|'s, the second set of references are |Lemma|'s and |
| 181 |
% the third set of references are |Theorem|'s. |
| 182 |
% The set of numbers for the |Definition|'s are increasing, |
| 183 |
% the set of numbers for the |Lemma|'s are increasing and |
| 184 |
% the set of numbers for the |Theorem|'s are increasing. |
| 185 |
% With more complicated coding, the names can be added and the lists compactified to get something line |
| 186 |
% |Theorems 1-3 and 5, Lemma 9 and Definitions 6, 8 and 12|. |
| 187 |
% |
| 188 |
% \subsection{\texorpdfstring{\copy\mm\tt permute}{permute}}\label{permute} |
| 189 |
% Use |\doublebubblesort| to apply a permutation to a stack/list. |
| 190 |
% A \emph{permutation} is an ordered stack/list of symbols which also has a natural order. |
| 191 |
% Popular symbol sets are positive integers and lowercase letters. The comparator macro needs |
| 192 |
% to sort a list of symbols with no repetitions back to its natural order. |
| 193 |
% A permutation $\pi$ can be given by listing the values of $\pi$ when applied to the symbols |
| 194 |
% in their natural order. For example $\pi$|={{5}{1}{2}{3}{4}}| means $\pi$|(1)=5|, $\pi$|(2)=1|, $\pi$|(3)=2|, $\pi$|(4)=3|, $\pi$|(5)=4|. |
| 195 |
% |
| 196 |
% At the end of line 2 of the displayed code below, |\ott| contains the symbols in their natural order |
| 197 |
% so |\permute| does not need to be told the symbols in advance. |
| 198 |
% At the end of line 3, |\ott| contains the inverse to the original permutation. |
| 199 |
% At the end of line 4, |#4| contains the permuted version of |#3|. |
| 200 |
% |
| 201 |
% \null\hskip0.13\textwidth \vbox{\begin{verbatim} |
| 202 |
% \newcommand{\permute}[4][\realSort]{% |
| 203 |
% \bubblesort[#1]{#2}{\ott}% |
| 204 |
% \doublebubblesort[#1]{#2}{\ott}{\ott}{\ott}% |
| 205 |
% \doublebubblesort[#1]{\ott}{\ott}{#3}{#4}% |
| 206 |
% } |
| 207 |
% \end{verbatim}} |
| 208 |
% If |\def\LL{{${a_1}$}{${a_2}$}{${a_3}$}{${a_4}$}{${a_5}$}}| then\\ |
| 209 |
% |\permute{{5}{1}{2}{3}{4}}{\LL}{}| yields |
| 210 |
% |
| 211 |
% {${\tt a}_5$}\, {${\tt a}_1$}\, {${\tt a}_2$}\, {${\tt a}_3$}\, {${\tt a}_4$}\ , which is |
| 212 |
% {${\tt a}_{\pi(1)}$}\, {${\tt a}_{\pi(2)}$}\, {${\tt a}_{\pi(3)}$}\, {${\tt a}_{\pi(4)}$}\, {${\tt a}_{\pi(5)}$}\ as desired. |
| 213 |
% \bigskip |
| 214 |
% |
| 215 |
% |\permute| can also be used to multiply permutations: |
| 216 |
% \begin{itemize} |
| 217 |
% \item |\permute{\pi_1}{\pi_2}{\ans}| yields |\pi_2|$\circ$|\pi_1| |
| 218 |
% \item |\permute{\pi_2}{\pi_1}{\ans}| yields |\pi_1|$\circ$|\pi_2|. |
| 219 |
% \end{itemize} |
| 220 |
% |
| 221 |
% \section{Implementation}\label{implementation} |
| 222 |
% Line numbers refer to the line numbers printed next to the code beginning with |\NeedsTeXFormat| \hyperlink{NeedsTeXFormat}{here}. |
| 223 |
% There are only four public macros, |\bubblesort| on line \codeRef{bubblesort} |
| 224 |
% and |\doublebubblesort| on line \codeRef{doublebubblesort} and comparator macros |\realSort| on line \codeRef{realSort}\ and |
| 225 |
% |\alphSort| on line \codeRef{alphSort}. |
| 226 |
% Private macros begin with |\@bubblesort@| to minimize the chance of name conflicts with other packages. |
| 227 |
% This makes reading the code somewhat tedious so |
| 228 |
% in the descriptions of the code below, the initial |\@bubblesort@| will be replaced by |*|. |
| 229 |
% |
| 230 |
% \subsection{\texorpdfstring{\copy\mm\tt bubblesort}{bubblesort}} |
| 231 |
% |\bubblesort[#1]{#2}{#3}|: |
| 232 |
% The implementation of |\bubblesort| begins by defining an empty |*rightList| and putting the stack/list to be sorted, |#2|, into |*workingList|. |
| 233 |
% Note |#2| is now safe - unless |#2| equals |#3|, |#2| will never change. |
| 234 |
% Then |\bubblesort| removes the leftmost item in |*workingList| |
| 235 |
% and saves it in |*testItem|. Then it moves on to |\@bubblesort@S| which does the recursion. |
| 236 |
% |
| 237 |
% First, |\bubblesort@S| (line \codeRef{bubblesortS}) sets an |etoolbox| boolean, |did a flip|, to false and sets |*leftList| to empty. |
| 238 |
% Then the macro removes the leftmost element in |*workingList| and saves it in |*nextItem|. |
| 239 |
% Then it enters the |while| loop (line \codeRef{while}). |
| 240 |
% The exit condition is that |*nextItem| is empty. |
| 241 |
% Then the comparator macro is evaluated on the ordered pair $\bigl($|*testItem| , |*nextItem|$\bigr)$. |
| 242 |
% The smaller of the pair is append to |*leftList| on the right and the larger is set to |*testItem|. |
| 243 |
% The loop continues until |*workingList| is empty. At this point |*testItem| contains the largest element in the |
| 244 |
% original |*workingList| and it is added to |*rightList| at the left end. |
| 245 |
% Hence |*leftList| followed by |*rightList| is the original list. |
| 246 |
% Next |*leftList| is put into |*workingList| and then the leftmost element is removed and put into |*testItem|. |
| 247 |
% Finally the |while| loop is reentered. |
| 248 |
% |
| 249 |
% After $k$ iterations of the |while| loop, |*rightList| has $k$ elements which are the $k$ largest elements in the original list in increasing order. |
| 250 |
% When the boolean |did a flip| is false, |*leftList| is also ordered so |*leftList| followed by |*rightList| is the original list sorted |
| 251 |
% and the |while| loop exits. |
| 252 |
% The sorted list and macro |#3| from |\bubblesort| are passed on to |\@bubblesort@output| which outputs the list as requested |
| 253 |
% and |\bubblesort| is finished. |
| 254 |
% |
| 255 |
% \noindent\textbf{Remark:} The reader who has worked through the discussion above will have noticed that this implementation of bubble sort |
| 256 |
% uses about four times the storage as the |C| version which sorts the array in place. |
| 257 |
% Stacks used in \LaTeX, are probably small enough that this is not a problem. |
| 258 |
% |
| 259 |
% Sorting a thousand item list of integers in reverse order (which is the worse case scenario) took less than sixty-five seconds running |
| 260 |
% |TexShop| |4.44| on a Mac 2013 Powerbook using timing code from |
| 261 |
% \href{https://tex.stackexchange.com/questions/456316/what-is-the-latex-equivalent-of-context-testfeatureonce-to-benchmark-performanc/456322#456322}{tex.stackexchange}. It put no strain on \TeX's memory allocations. |
| 262 |
% |
| 263 |
% \bigskip |
| 264 |
% \subsection{\texorpdfstring{\copy\mm\tt doublebubblesort}{doublebubblesort}} |
| 265 |
% |\doublebubblesort[#1]{#2}{#3}{#4}{#5}|: |
| 266 |
% The |\doublebubblesort| (line \codeRef{doublebubblesort}), |\@doublebubblesort@S| (line \codeRef{doublebubblesortS}), |
| 267 |
% macros work much like |\bubblesort|, |\@bubblesort@S|. |
| 268 |
% The code in the |double|'d version contains the identical code from |\bubblesort|, |\@bubblesort@S| except that |A| is added |
| 269 |
% to the end of each of the internal macros. There is also a parallel copy of macros with |B| added and everything done with the |
| 270 |
% |A| variables is mimicked with the |B| variables. |
| 271 |
% |
| 272 |
% \bigskip |
| 273 |
% \subsection{The remaining macros} |
| 274 |
% The macro |\@bubblesort@output#1#2| (line \codeRef{output}) is just to shorten the code |
| 275 |
% since there are three places a stack or a list is output (lines \codeRef{outputA}, \codeRef{outputB} and \codeRef{outputC}). |
| 276 |
% |
| 277 |
% The macro |\@bubblesort@EoS| is the End-of-Stack indicator. |
| 278 |
% |
| 279 |
% The remaining macros do the removing items from a list and inserting items at either end of a list. |
| 280 |
% The shift macro is \\ |
| 281 |
% \null\hskip1in|\@bubblesort@shift#1#2\@bubblesort@EoS#3#4| (line \codeRef{shiftM})\\ |
| 282 |
% which is used as \\|\expandafter\@bubblesort@shift{stack/list}\@bubblesort@EoS{\itemA}{\itemB}| which |
| 283 |
% puts the leftmost item in the stack/list into |\itemA| and the rest of the stack/list into |\itemB|. |
| 284 |
% |
| 285 |
% The macros |\@bubblesort@rightappendItem| (line \codeRef{rAi}) \\and |
| 286 |
% |\@bubblesort@lefttappendItem| (line \codeRef{lAi}) are identical to Knuth's |
| 287 |
% |\rightappenditem| and |\leftappenditem| except that there are no prepended |\\|'s. |
| 288 |
% |
| 289 |
% \StopEventually{} |
| 290 |
% \color{white} |
| 291 |
% \setcounter{CodelineNo}{15} |
| 292 |
% \begin{macro}{blank}\color{black}\textbf{Start of code:} |
| 293 |
% \hypertarget{NeedsTeXFormat}{} |
| 294 |
% The rest of the file from the end of this paragraph onward is a copy of the file |
| 295 |
% generated by \TeX ing the |bubblesort.ins| file except that the standard set of comments |
| 296 |
% at the start of an |ins| generated file are omitted. And of course the line numbers on the left here are |
| 297 |
% not present in the |\bubblesort.sty| file. |
| 298 |
% The comments portion takes 15 lines. |
| 299 |
% Most editors show line numbers and allow line number navigation so it has been arranged that |
| 300 |
% the line numbers in the typeset |bubblesort.dtx| file below match the line numbers |
| 301 |
% in the |ins|-generated |bubblesort.sty| file. |
| 302 |
% \begin{macrocode} |
| 303 |
\NeedsTeXFormat{LaTeX2e}[2005/12/01] |
| 304 |
\ProvidesPackage{bubblesort} |
| 305 |
[2020/07/01 v1.0 implements a bubble sort] |
| 306 |
|
| 307 |
\RequirePackage{etoolbox} |
| 308 |
|
| 309 |
\makeatletter |
| 310 |
|
| 311 |
\newcount\bubblesortflag |
| 312 |
\newbool{did a flip} |
| 313 |
\def\@bubblesort@EoS{}% End-of-Stack indicator |
| 314 |
|
| 315 |
% \end{macrocode} \LabelLine{realSort} |
| 316 |
\def\realSort#1#2{% |
| 317 |
\ifdimless{#2 pt}{#1 pt}{\bubblesortflag=1}{\bubblesortflag=-1}} |
| 318 |
% \end{macrocode} \LabelLine{alphSort} |
| 319 |
\def\alphSort#1#2{\ifnumequal{\pdfstrcmp{#1}{#2}}{1}% |
| 320 |
{\bubblesortflag=1}{\bubblesortflag=-1}} |
| 321 |
% \end{macrocode} \LabelLine{bubblesort} |
| 322 |
\newcommand{\bubblesort}[3][\realSort]{% |
| 323 |
%% #1 comparator macro, #2 input stack/list, #3 answer list: #2=#3 OK |
| 324 |
\def\@bubblesort@rightList{}% |
| 325 |
\expandafter\@bubblesort@shiftOne#2{}{}{}\@bubblesort@EoS{% |
| 326 |
\@bubblesort@testItem}{\@bubblesort@workingList}% |
| 327 |
\expandafter\@bubblesort@S{#3}{#1}% |
| 328 |
} |
| 329 |
% \end{macrocode} \LabelLine{bubblesortS} |
| 330 |
\def\@bubblesort@S#1#2{% #1 is name for answer --- #2 is comparator macro |
| 331 |
\boolfalse{did a flip}\def\@bubblesort@leftList{}% |
| 332 |
\expandafter\@bubblesort@shiftOne\@bubblesort@workingList{}{}\@bubblesort@EoS{% |
| 333 |
\@bubblesort@nextItem}{\@bubblesort@workingList}% |
| 334 |
% \end{macrocode} \Label{while}\nointerlineskip\begin{macrocode} |
| 335 |
\whileboolexpr{not test{\ifdefvoid{\@bubblesort@nextItem}}}{% |
| 336 |
#2{\@bubblesort@testItem}{\@bubblesort@nextItem}\relax% |
| 337 |
\ifnumequal{\bubblesortflag}{1}{% flip |
| 338 |
\booltrue{did a flip}% |
| 339 |
\expandafter\@bubblesort@rightappendItem\expandafter{\@bubblesort@nextItem}% |
| 340 |
\to\@bubblesort@leftList% |
| 341 |
}{% |
| 342 |
\expandafter\@bubblesort@rightappendItem\expandafter{\@bubblesort@testItem}% |
| 343 |
\to\@bubblesort@leftList% |
| 344 |
\expandafter\def\expandafter\@bubblesort@testItem\expandafter{\@bubblesort@nextItem}% |
| 345 |
}% |
| 346 |
\expandafter\@bubblesort@shiftOne\@bubblesort@workingList\@bubblesort@EoS{% |
| 347 |
\@bubblesort@nextItem}{\@bubblesort@workingList}% |
| 348 |
}% |
| 349 |
\expandafter\leftappendItem\expandafter{\@bubblesort@testItem}\to\@bubblesort@rightList% |
| 350 |
\ifbool{did a flip}{% |
| 351 |
\expandafter\def\expandafter\@bubblesort@workingList\expandafter% |
| 352 |
{\@bubblesort@leftList{}{}{}}% |
| 353 |
\expandafter\@bubblesort@shiftOne\@bubblesort@workingList\@bubblesort@EoS{% |
| 354 |
\@bubblesort@testItem}{\@bubblesort@workingList}% |
| 355 |
\def\@bubblesort@leftList{}% |
| 356 |
\@bubblesort@S{#1}{#2}}% |
| 357 |
% \end{macrocode} \Label{outputA}\nointerlineskip\begin{macrocode} |
| 358 |
{\@bubblesort@output{#1}{\@bubblesort@leftList\@bubblesort@rightList}% |
| 359 |
}} |
| 360 |
% \end{macrocode} \Label{output}\nointerlineskip\begin{macrocode} |
| 361 |
\def\@bubblesort@output#1#2{% #1 name of output list or empty --- #2 sorted stack |
| 362 |
\ifstrempty{#1}% |
| 363 |
{#2}{\expandafter\edef\expandafter#1\expandafter{#2}}% |
| 364 |
} |
| 365 |
% \end{macrocode} \Label{doublebubblesort}\nointerlineskip\begin{macrocode} |
| 366 |
\newcommand{\doublebubblesort}[5][\realSort]{% |
| 367 |
%% #1 comparator macro |
| 368 |
%% #2 input stack/list --- #3 output for #2 stack/list; #2=#3 OK |
| 369 |
%% #4 second stack/list --- #5 answer list for #4; #4=#5 OK |
| 370 |
\def\@bubblesort@rightListA{}\def\@bubblesort@rightListB{}% |
| 371 |
\expandafter\@bubblesort@shiftOne#2{}{}{}\@bubblesort@EoS{% |
| 372 |
\@bubblesort@testItemA}{\@bubblesort@workingListA}% |
| 373 |
\expandafter\@bubblesort@shiftOne#4{}{}{}\@bubblesort@EoS{% |
| 374 |
\@bubblesort@testItemB}{\@bubblesort@workingListB}% |
| 375 |
\expandafter\@doublebubblesort@S{#3}{#5}{#1}% |
| 376 |
} |
| 377 |
% \end{macrocode} \Label{doublebubblesortS}\nointerlineskip\begin{macrocode} |
| 378 |
\def\@doublebubblesort@S#1#2#3{% |
| 379 |
%% #1 output for sorted stack/list --- #2 output for ``sorted'' stack/list |
| 380 |
%% #3 comparator macro |
| 381 |
\boolfalse{did a flip}\def\@bubblesort@leftListA{}\def\@bubblesort@leftListB{}% |
| 382 |
\expandafter\@bubblesort@shiftOne\@bubblesort@workingListA{}{}% |
| 383 |
\@bubblesort@EoS{\@bubblesort@nextItemA}{\@bubblesort@workingListA}% |
| 384 |
\expandafter\@bubblesort@shiftOne\@bubblesort@workingListB{}{}% |
| 385 |
\@bubblesort@EoS{\@bubblesort@nextItemB}{\@bubblesort@workingListB}% |
| 386 |
\whileboolexpr{not test{\ifdefvoid{\@bubblesort@nextItemA}}}{% |
| 387 |
#3{\@bubblesort@testItemA}{\@bubblesort@nextItemA}\relax% |
| 388 |
\ifnumequal{\bubblesortflag}{1}{% flip |
| 389 |
\booltrue{did a flip}% |
| 390 |
\expandafter\@bubblesort@rightappendItem\expandafter{% |
| 391 |
\@bubblesort@nextItemA}\to\@bubblesort@leftListA% |
| 392 |
\expandafter\@bubblesort@rightappendItem\expandafter{% |
| 393 |
\@bubblesort@nextItemB}\to\@bubblesort@leftListB% |
| 394 |
}{% |
| 395 |
\expandafter\@bubblesort@rightappendItem\expandafter{% |
| 396 |
\@bubblesort@testItemA}\to\@bubblesort@leftListA% |
| 397 |
\expandafter\@bubblesort@rightappendItem\expandafter{% |
| 398 |
\@bubblesort@testItemB}\to\@bubblesort@leftListB% |
| 399 |
\expandafter\def\expandafter\@bubblesort@testItemA\expandafter{% |
| 400 |
\@bubblesort@nextItemA}% |
| 401 |
\expandafter\def\expandafter\@bubblesort@testItemB\expandafter{% |
| 402 |
\@bubblesort@nextItemB}% |
| 403 |
}% |
| 404 |
\expandafter\@bubblesort@shiftOne\@bubblesort@workingListA\@bubblesort@EoS{% |
| 405 |
\@bubblesort@nextItemA}{\@bubblesort@workingListA}% |
| 406 |
\expandafter\@bubblesort@shiftOne\@bubblesort@workingListB\@bubblesort@EoS{% |
| 407 |
\@bubblesort@nextItemB}{\@bubblesort@workingListB}% |
| 408 |
}% |
| 409 |
\expandafter\leftappendItem\expandafter{\@bubblesort@testItemA}\to% |
| 410 |
\@bubblesort@rightListA% |
| 411 |
\expandafter\leftappendItem\expandafter{\@bubblesort@testItemB}\to% |
| 412 |
\@bubblesort@rightListB% |
| 413 |
\ifbool{did a flip}{% |
| 414 |
\expandafter\def\expandafter\@bubblesort@workingListA\expandafter{% |
| 415 |
\@bubblesort@leftListA{}{}{}}% |
| 416 |
\expandafter\def\expandafter\@bubblesort@workingListB\expandafter{% |
| 417 |
\@bubblesort@leftListB{}{}{}}% |
| 418 |
\expandafter\@bubblesort@shiftOne\@bubblesort@workingListA\@bubblesort@EoS{% |
| 419 |
\@bubblesort@testItemA}{\@bubblesort@workingListA}% |
| 420 |
\expandafter\@bubblesort@shiftOne\@bubblesort@workingListB\@bubblesort@EoS{% |
| 421 |
\@bubblesort@testItemB}{\@bubblesort@workingListB}% |
| 422 |
\def\@bubblesort@leftListA{}% |
| 423 |
\def\@bubblesort@leftListB{}% |
| 424 |
\expandafter\@doublebubblesort@S{#1}{#2}{#3}}% |
| 425 |
% \end{macrocode} \Label{outputB}\nointerlineskip\begin{macrocode} |
| 426 |
{\@bubblesort@output{#1}{\@bubblesort@leftListA\@bubblesort@rightListA}% |
| 427 |
% \end{macrocode} \Label{outputC}\nointerlineskip\begin{macrocode} |
| 428 |
\@bubblesort@output{#2}{\@bubblesort@leftListB\@bubblesort@rightListB}}% |
| 429 |
} |
| 430 |
|
| 431 |
% \end{macrocode} \Label{shiftM}\nointerlineskip\begin{macrocode} |
| 432 |
\def\@bubblesort@shiftOne#1#2\@bubblesort@EoS#3#4{% |
| 433 |
\expandafter\gdef\expandafter#3\expandafter{#1}% |
| 434 |
\expandafter\gdef\expandafter#4\expandafter{#2}% |
| 435 |
} |
| 436 |
|
| 437 |
\newtoks\ta\newtoks\tb |
| 438 |
% \end{macrocode} \Label{rAi}\nointerlineskip\begin{macrocode} |
| 439 |
\long\def\@bubblesort@rightappendItem#1\to#2{\ta={{#1}}\tb=\expandafter{#2}% |
| 440 |
\edef#2{\the\tb\the\ta}} |
| 441 |
% \end{macrocode} \Label{lAi}\nointerlineskip\begin{macrocode} |
| 442 |
\long\def\leftappendItem#1\to#2{\ta={{#1}}\tb=\expandafter{#2}% |
| 443 |
\edef#2{\the\ta\the\tb}} |
| 444 |
\makeatother |
| 445 |
\endinput |
| 446 |
% \end{macrocode} |
| 447 |
% \end{macro} |
| 448 |
% \Finale |