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

\RequirePackage{etoolbox}

\makeatletter

\newcount\bubblesortflag
\newbool{did a flip}
\def\@bubblesort@EoS{}% End-of-Stack indicator

%    \end{macrocode} \LabelLine{realSort}
\def\realSort#1#2{%
\ifdimless{#2 pt}{#1 pt}{\bubblesortflag=1}{\bubblesortflag=-1}}
%    \end{macrocode} \LabelLine{alphSort}
\def\alphSort#1#2{\ifnumequal{\pdfstrcmp{#1}{#2}}{1}%
{\bubblesortflag=1}{\bubblesortflag=-1}}
%    \end{macrocode} \LabelLine{bubblesort}
\newcommand{\bubblesort}[3][\realSort]{%
%% #1 comparator macro, #2 input stack/list, #3 answer list: #2=#3 OK
\def\@bubblesort@rightList{}%
\expandafter\@bubblesort@shiftOne#2{}{}{}\@bubblesort@EoS{%
\@bubblesort@testItem}{\@bubblesort@workingList}%
\expandafter\@bubblesort@S{#3}{#1}%
}
%    \end{macrocode} \LabelLine{bubblesortS}
\def\@bubblesort@S#1#2{% #1 is name for answer --- #2 is comparator macro
\boolfalse{did a flip}\def\@bubblesort@leftList{}%
\expandafter\@bubblesort@shiftOne\@bubblesort@workingList{}{}\@bubblesort@EoS{%
\@bubblesort@nextItem}{\@bubblesort@workingList}%
%    \end{macrocode} \Label{while}\nointerlineskip\begin{macrocode}
\whileboolexpr{not test{\ifdefvoid{\@bubblesort@nextItem}}}{%
#2{\@bubblesort@testItem}{\@bubblesort@nextItem}\relax%
\ifnumequal{\bubblesortflag}{1}{% flip
\booltrue{did a flip}%
\expandafter\@bubblesort@rightappendItem\expandafter{\@bubblesort@nextItem}%
\to\@bubblesort@leftList%
}{%
\expandafter\@bubblesort@rightappendItem\expandafter{\@bubblesort@testItem}%
\to\@bubblesort@leftList%
\expandafter\def\expandafter\@bubblesort@testItem\expandafter{\@bubblesort@nextItem}%
}%
\expandafter\@bubblesort@shiftOne\@bubblesort@workingList\@bubblesort@EoS{%
\@bubblesort@nextItem}{\@bubblesort@workingList}%
}%
\expandafter\leftappendItem\expandafter{\@bubblesort@testItem}\to\@bubblesort@rightList%
\ifbool{did a flip}{%
\expandafter\def\expandafter\@bubblesort@workingList\expandafter%
{\@bubblesort@leftList{}{}{}}%
\expandafter\@bubblesort@shiftOne\@bubblesort@workingList\@bubblesort@EoS{%
\@bubblesort@testItem}{\@bubblesort@workingList}%
\def\@bubblesort@leftList{}%
\@bubblesort@S{#1}{#2}}%
%    \end{macrocode} \Label{outputA}\nointerlineskip\begin{macrocode}
{\@bubblesort@output{#1}{\@bubblesort@leftList\@bubblesort@rightList}%
}}
%    \end{macrocode} \Label{output}\nointerlineskip\begin{macrocode}
\def\@bubblesort@output#1#2{% #1 name of output list or empty ---  #2 sorted stack
\ifstrempty{#1}%
{#2}{\expandafter\edef\expandafter#1\expandafter{#2}}%
}
%    \end{macrocode} \Label{doublebubblesort}\nointerlineskip\begin{macrocode}
\newcommand{\doublebubblesort}[5][\realSort]{%
%% #1 comparator macro
%% #2 input stack/list  --- #3 output for #2 stack/list; #2=#3 OK
%% #4 second stack/list --- #5 answer list for #4; #4=#5 OK
\def\@bubblesort@rightListA{}\def\@bubblesort@rightListB{}%
\expandafter\@bubblesort@shiftOne#2{}{}{}\@bubblesort@EoS{%
\@bubblesort@testItemA}{\@bubblesort@workingListA}%
\expandafter\@bubblesort@shiftOne#4{}{}{}\@bubblesort@EoS{%
\@bubblesort@testItemB}{\@bubblesort@workingListB}%
\expandafter\@doublebubblesort@S{#3}{#5}{#1}%
}
%    \end{macrocode} \Label{doublebubblesortS}\nointerlineskip\begin{macrocode}
\def\@doublebubblesort@S#1#2#3{%
%% #1 output for sorted stack/list --- #2 output for ``sorted'' stack/list 
%% #3 comparator macro
\boolfalse{did a flip}\def\@bubblesort@leftListA{}\def\@bubblesort@leftListB{}%
\expandafter\@bubblesort@shiftOne\@bubblesort@workingListA{}{}%
\@bubblesort@EoS{\@bubblesort@nextItemA}{\@bubblesort@workingListA}%
\expandafter\@bubblesort@shiftOne\@bubblesort@workingListB{}{}%
\@bubblesort@EoS{\@bubblesort@nextItemB}{\@bubblesort@workingListB}%
\whileboolexpr{not test{\ifdefvoid{\@bubblesort@nextItemA}}}{%
#3{\@bubblesort@testItemA}{\@bubblesort@nextItemA}\relax%
\ifnumequal{\bubblesortflag}{1}{% flip
\booltrue{did a flip}%
\expandafter\@bubblesort@rightappendItem\expandafter{%
\@bubblesort@nextItemA}\to\@bubblesort@leftListA%
\expandafter\@bubblesort@rightappendItem\expandafter{%
\@bubblesort@nextItemB}\to\@bubblesort@leftListB%
}{%
\expandafter\@bubblesort@rightappendItem\expandafter{%
\@bubblesort@testItemA}\to\@bubblesort@leftListA%
\expandafter\@bubblesort@rightappendItem\expandafter{%
\@bubblesort@testItemB}\to\@bubblesort@leftListB%
\expandafter\def\expandafter\@bubblesort@testItemA\expandafter{%
\@bubblesort@nextItemA}%
\expandafter\def\expandafter\@bubblesort@testItemB\expandafter{%
\@bubblesort@nextItemB}%
}%
\expandafter\@bubblesort@shiftOne\@bubblesort@workingListA\@bubblesort@EoS{%
\@bubblesort@nextItemA}{\@bubblesort@workingListA}%
\expandafter\@bubblesort@shiftOne\@bubblesort@workingListB\@bubblesort@EoS{%
\@bubblesort@nextItemB}{\@bubblesort@workingListB}%
}%
\expandafter\leftappendItem\expandafter{\@bubblesort@testItemA}\to%
\@bubblesort@rightListA%
\expandafter\leftappendItem\expandafter{\@bubblesort@testItemB}\to%
\@bubblesort@rightListB%
\ifbool{did a flip}{%
\expandafter\def\expandafter\@bubblesort@workingListA\expandafter{%
\@bubblesort@leftListA{}{}{}}%
\expandafter\def\expandafter\@bubblesort@workingListB\expandafter{%
\@bubblesort@leftListB{}{}{}}%
\expandafter\@bubblesort@shiftOne\@bubblesort@workingListA\@bubblesort@EoS{%
\@bubblesort@testItemA}{\@bubblesort@workingListA}%
\expandafter\@bubblesort@shiftOne\@bubblesort@workingListB\@bubblesort@EoS{%
\@bubblesort@testItemB}{\@bubblesort@workingListB}%
\def\@bubblesort@leftListA{}%
\def\@bubblesort@leftListB{}%
\expandafter\@doublebubblesort@S{#1}{#2}{#3}}%
%    \end{macrocode} \Label{outputB}\nointerlineskip\begin{macrocode}
{\@bubblesort@output{#1}{\@bubblesort@leftListA\@bubblesort@rightListA}%
%    \end{macrocode} \Label{outputC}\nointerlineskip\begin{macrocode}
\@bubblesort@output{#2}{\@bubblesort@leftListB\@bubblesort@rightListB}}%
}

%    \end{macrocode} \Label{shiftM}\nointerlineskip\begin{macrocode}
\def\@bubblesort@shiftOne#1#2\@bubblesort@EoS#3#4{%
\expandafter\gdef\expandafter#3\expandafter{#1}%
\expandafter\gdef\expandafter#4\expandafter{#2}%
}

\newtoks\ta\newtoks\tb
%    \end{macrocode} \Label{rAi}\nointerlineskip\begin{macrocode}
\long\def\@bubblesort@rightappendItem#1\to#2{\ta={{#1}}\tb=\expandafter{#2}%
\edef#2{\the\tb\the\ta}}
%    \end{macrocode} \Label{lAi}\nointerlineskip\begin{macrocode}
\long\def\leftappendItem#1\to#2{\ta={{#1}}\tb=\expandafter{#2}%
\edef#2{\the\ta\the\tb}}
\makeatother
\endinput
%    \end{macrocode} 
% \end{macro}
% \Finale