Debian Codegraph @

texmf-dist/source/latex/bubblesort/bubblesort.dtx

raw
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