summaryrefslogtreecommitdiff
path: root/macros/latex/contrib/bubblesort/bubblesort.dtx
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2020-07-02 03:03:05 +0000
committerNorbert Preining <norbert@preining.info>2020-07-02 03:03:05 +0000
commitc2b7c45f7c8c093b8bc730da9abaa919d8327491 (patch)
tree640532738a3185f8a21d3080746e2a87059f9577 /macros/latex/contrib/bubblesort/bubblesort.dtx
parentd79a721c345c9a2ced6c0640e88c10cc3378c1f0 (diff)
CTAN sync 202007020303
Diffstat (limited to 'macros/latex/contrib/bubblesort/bubblesort.dtx')
-rw-r--r--macros/latex/contrib/bubblesort/bubblesort.dtx448
1 files changed, 448 insertions, 0 deletions
diff --git a/macros/latex/contrib/bubblesort/bubblesort.dtx b/macros/latex/contrib/bubblesort/bubblesort.dtx
new file mode 100644
index 0000000000..a96fe27fb6
--- /dev/null
+++ b/macros/latex/contrib/bubblesort/bubblesort.dtx
@@ -0,0 +1,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