25

I'm trying to implement a (quick) sort algorithm. Here is what I can do :

\documentclass[preview, border=7mm]{standalone}
\usepackage{pgffor}

% \push{xs}{\i} add \i in the array \xs 
\def\push#1#2{\expandafter\xdef\csname #1\endcsname{\expandafter\ifx\csname #1\endcsname\empty\else\csname #1\endcsname,\fi#2}}

\newcommand*{\qsort}[1]{%
  \edef\arr{#1}% the array to sort
  \foreach[count=\len] \i in \arr{}% take the length
  \ifnum\len>1\relax% if 0 or 1 elements in the array, nothing to sort
    \pgfmathsetmacro\midval{{\arr}[int(\len/2)]}% take the middle element (a random one is probably better) as pivot
    \let\xs\empty\let\xe\empty\let\xl\empty% \xs (s for small), \xe (e for equal), \xl (l for large)
    \foreach \i in \arr{%
      \ifdim \i pt < \midval pt%
        \push{xs}{\i}% if \i < pivot, push it in \xs
      \else%
        \ifdim \i pt = \midval pt%
          \push{xe}{\i}% if \i = pivot, push it in \xe
        \else%
          \push{xl}{\i}% if \i > pivot, push it in \xl
        \fi%
      \fi%
    }%
    \edef\nxs{\xs}\edef\nxe{\xe}\edef\nxl{\xl}% save the globals
    \ifx\nxs\empty\else{\qsort\nxs},\fi% cal qsort for \nxs if not empty
    \nxe% copy \nxe (in general containing only the pivot element)
    \ifx\nxl\empty\else,{\qsort\nxl}\fi% cal qsort for \nxl if not empty
  \else%
    \arr% 0 or 1 element array is already sorted
  \fi%
}
\begin{document}
  \let\temp\empty
  \foreach \i in {1,...,10}{\pgfmathparse{rnd}\push{temp}{\pgfmathresult}}
  \temp\newline
  when sorted becomes\newline
  \qsort\temp
\end{document}

enter image description here

My main problem is that due to \foreach this macro is not expandable. So I can't make \edef\sorted{\qsort\data}.

So my questions is : How can I define an expandable (quick) sort, working with arrays like {.1,10,.25} ?

Precision: I have put 'quick' in parentheses, because for me the most important is to be expandable. My other criteria are : to be, if possible, short and, if possible, fast.

  • 3
    Do you really need it to be expandable? Any fully expandable version will be painfully slow and I'm not sure QuickSort can be done expandably. – egreg Oct 14 '15 at 21:40
  • 2
    There is an implementation of (non-expandable) quicksort in the forest package. Write to me if you'll use it and have trouble understanding the interface, as it's not terribly well documented. – Sašo Živanović Oct 14 '15 at 22:30
  • 1
    l3sort has it implemented. Altough it's still experimental so I'm not sure if that means it works or not. – Manuel Oct 15 '15 at 1:03
  • 1
    @SašoŽivanović thanks, but my code is also a non expandable 'quick sort' (it works). My need is expandable (not necessarily 'quick'). – Kpym Oct 15 '15 at 5:18
  • 1
    @LoopSpace I know (see my first comment after John Kormylo's answer). I know also that we can in 99% avoid to have fully expandable things. But I like the idea to be able to put anywhere \qsort{1,3,2} in place of {1,2,3}. And I don't like \pgfmathparse{...} followed by \pgfmathresult, but I use it a lot ;) – Kpym Oct 18 '15 at 10:50
34
+500

This answer has four five six four routines:

the last update: leaner code 6, as I understand better my hacky use of \pdfescapestring and could remove some superfluous extras (if they had been really needed, these extras would not have been enough anyhow).

the very last update: improved sub-routine for merging in code 6 bringing at least a 2x speed increase.

  1. the first one is the direct adaptation of the code to be found in the xint.pdf documentation since 2013/10/29 release; at the start of section 7.28 The Quick Sort algorithm illustrated there is an expandable implementation of the QuickSort algorithm. As it handled braced items, rather than comma separated ones, I needed to add conversion back and forth from comma separated values to braced items. This code uses xinttools for list utilities and xintfrac for comparison of "real" numbers.

  2. the second code treats directly the comma separated values. No need for package xinttools anymore. Still uses xintfrac, and needs release 1.2 due to using \xintdothis/\xintorthat which in earlier releases exist under names containing _ only. It is more efficient than code version 1 also because it does less comparisons (code 1 does each comparison thrice (!!!), code 2 only twice).

  3. Code 1 and 2 are kept only for sentimental reasons. The third code is a variant of code 2 which does each comparison only once, thus I expect it to be about twice faster. But for very long inputs, perhaps it has a penalty from longer token lists. Uses xintfrac 1.2 as code 2.

  4. the fourth code is exactly like code 3, but rather than xintfrac it assumes the numbers may be compared with \ifdim. Thus this last code requires no package whatsoever. Needless to say it is faster too. But prone to Dimension too large error if the input does not fit.

    The previous update was to allow codes 2, 3, 4 to accept empty input (not empty values, only empty global input) gracefully.

  5. the fifth and final one handles alphabetical inputs either with \pdfstrcmp (under pdflatex) or with \strcmp (under XeTeX). For a change, this variant expands completely only in an \edef (or \message, etc..), a full expansion of the first token is not enough contrarily to what 1, 2, 3, 4 offer. Empty or blank items in the input will be discarded from output, initial spaces are removed and each comma of the output has exactly one space after it. Final spaces of items (before commas) are left as they are (this will mean most of the time exactly one space token, as it requires special circumstances to create inputs with multiple space tokens in a row). It is not hard to modify the code to act like 1, 2, 3, 4 and not require \edef so as to allow items which are macros which one does not want to see expanded in the output.

    A hopefully final edit improves a bit the speed of code 5 as it exploits the fact that the blanks are gone after the first pass.

  6. The sixth one is an expandable implementation of the Merge Sort algorithm, in a bottom up variant. For expandability, I could have gone the top down way, but that would require (at least in a simple-minded approach) a count of items to separate in two parts, and then recursively. I opted for a bottom-up approach, which a priori causes grave problems of implementations in an expandable way (**), problems which are solved by a trick for propagating expansion which I learned from correspondance with Bruno Le Floch: the trick is to use the pdftex primitive \pdfescapestring. In this manner I can make successive passes, first two by two, then four by four, then eight by eight, each time leaving behind the already treated material. Other techniques are available but this would populate irreversibly parts of TeX memory.

    There is an inconvenience which is that spaces end up escaped. Thus I suppress them in the first pass and the final output has no spaces contrarily to the other methods: they can be added in a final pass. I give the code for sorting decimal numbers comparable with \ifdim. One could use xintfrac for arbitrary precision decimals or fractions. A first pass would apply \xintRaw to each item, to convert scientific notation to xintfrac A/B[N] notation, because the e would get catcode 12 from \pdfescapestring and on the next pass, this would not be recognized (alternative is to do the comparison in \xintthefloatexpr...\relax where the catcode of e does not matter).

    This method needs explicit inputs, it will fail on \a, \b, \c, \d case.

    (**) not problems of principle, but problems of efficiency: it would be possible to keep all tokens upfront, especially as we essentially only have to grab each time two more delimited things. For this we could temporarily put the already parsed material beyond the new two things, merge them, and then swap back at the end of the parsed stuff (if we want to maintain a stable sort). This means lots of token shuffling, which is precisely the thing we want to minimize when possibly handling thousands of tokens.

I haven' much tested the sixth code, but it appears to be the fastest one. Almost 6x faster than code 4 on a test with 1000 decimal numbers abcd.wxyz (after the improvement brought with last update).

because my answer was exceeding the maximal size I have deleted code 1 and code 2 to make room for code 6

All quicksort variants pick each time the first element as pivot, which is bad if the input is already close to sorted (or reverse sorted).

The mergesort has no such issues.


code 1 (removed)

Blockquote


code 2 (removed)

enter image description here


code 3

\documentclass{article}
\usepackage{color}
\usepackage[straightquotes]{newtxtt}
%\usepackage{xinttools}
\usepackage{xintfrac}

% THE QUICK SORT ALGORITHM EXPANDABLY
% adapted from xint.pdf user manual 
% to act on comma separated values.

% this second variant does not do twice comparison tests, hence should
% be about 2x faster at least for not extremely long inputs.

\makeatletter
% not needed for numerical inputs
% \catcode`! 3
% \catcode`? 3
\def\QSfull {\romannumeral0\qsfull }%
% first we check if empty list (else \qsfull@finish will not find a comma)
\def\qsfull   #1{\expandafter\qsfull@a\romannumeral-`0#1,!,?}%
\def\qsfull@a #1{\ifx,#1\expandafter\qsfull@abort\else
                        \expandafter\qsfull@start\fi #1}%
\def\qsfull@abort #1?{ }%
\def\qsfull@start {\expandafter\qsfull@finish\romannumeral0\qsfull@b,}%
\def\qsfull@finish ,#1{ #1}%
%
%
% we check if empty of single and if not pick up the first as Pivot:
\def\qsfull@b ,#1#2,#3{\ifx?#3\xintdothis\qsfull@empty\fi
                   \ifx!#3\xintdothis\qsfull@single\fi
                   \xintorthat \qsfull@separate {}{}{#1#2}#3}%
\def\qsfull@empty  #1#2#3#4{ }%
\def\qsfull@single #1#2#3#4?{, #3}%
\def\qsfull@separate #1#2#3#4#5,%
{%
    \ifx!#4\expandafter\qsfull@separate@done\fi
    \romannumeral0\xintifgt {#4#5}{#3}%
          \qsfull@separate@appendtogreater
          \qsfull@separate@appendtosmaller {#4#5}{#1}{#2}{#3}%
}%
%
\def\qsfull@separate@appendtogreater #1#2{\qsfull@separate {#2,#1}}%
\def\qsfull@separate@appendtosmaller #1#2#3{\qsfull@separate {#2}{#3,#1}}%
%
\def\qsfull@separate@done\romannumeral0\xintifgt #1#2%
    \qsfull@separate@appendtogreater
    \qsfull@separate@appendtosmaller #3#4#5#6?%
{%
    \expandafter\qsfull@f\expandafter
    {\romannumeral0\qsfull@b #4,!,?}{\qsfull@b #5,!,?}{#2}%
}%
%
\def\qsfull@f #1#2#3{#2, #3#1}%
%
% \catcode`! 12
% \catcode`? 12
\makeatother

\begin{document}\thispagestyle{empty}\pagestyle{empty}
% EXAMPLE

\ttfamily

First example:

\edef\z {\QSfull {1.0, 0.5  ,0.3, 1.5  ,1.8,2.0,1.7, 0.4, 1.2, 1.4,
    1.3, 1.1, 0.7, 1.6, 0.6, 0.9, 0.8, 0.2  ,   0.1    ,1.9}}

1.0, 0.5  ,0.3, 1.5  ,1.8,2.0,1.7, 0.4, 1.2, 1.4,
    1.3, 1.1, 0.7, 1.6, 0.6, 0.9, 0.8, 0.2  ,   0.1    ,1.9

will give macro with meaning (notice that the output has the same extra spaces
after digits and before commas that the user may have left on input; this is a
feature, not a bug; on the other hand commas on output always are followed by a
space, again a feature).

\meaning\z

\bigskip
\clearpage

First example:
\begin{verbatim}
\def\a {3.123456789123456789}
\def\b {3.123456789123456788}
\def\c {3.123456789123456790}
\def\d {3.123456789123456787}
% \oodef expands exactly twice the replacement text.
\oodef\z {\QSfull { \a, \b, \c, \d}}
% The first item \a is prefixed by a space to avoid being expanded on input
\meaning\z\par
% with \fdef (faster than \oodef), we use lowercase \qsfull which inserts a
% space hence this will stop the \romannumeral-`0 from the \fdef and avoid
% expansion of the first item of output.
\fdef\w {\qsfull { \a, \b, \c, \d}}
\meaning\w\par
\end{verbatim}

\def\a {3.123456789123456789}
\def\b {3.123456789123456788}
\def\c {3.123456789123456790}
\def\d {3.123456789123456787}

\oodef\z {\QSfull { \a, \b, \c, \d}}% The \a is prefixed by a space not be
                                % expanded

\textcolor{blue}{\meaning\z}

\fdef\w {\qsfull { \a, \b, \c, \d}}
\textcolor{blue}{\meaning\w}

\bigskip

% Third example:
% \begin{verbatim}
% \edef\z {\QSfull {0.7, 0.5, 0.9, 0.1, 1.32, 1.31, 0.11, 0.12, 0.1}}

% \meaning\z
% \end{verbatim}
% \fdef\z {\QSfull {0.7, 0.5, 0.9, 0.1, 1.32, 1.31, 0.11, 0.12, 0.1}}

% \meaning\z

Second Example:
\begin{verbatim}
\edef\z{\QSfull {513653, 408866, 886204, 735578, 608552, 412004, 186578,
140974, 649711, 465136, 388683, 323362, 504730, 254715, 195793, 233621, 671299,
428170, 951423, 653603, 665197, 857787, 771700, 992045, 372838, 929992, 167911,
780076, 243286, 69869, 804743, 300412, 530086, 173893, 900738, 493815, 9980,
448301, 824577, 514010, 522537, 919250, 986196, 774531, 240895, 956406, 685109,
604079, 736896, 111898, 682533, 542445, 674548, 889917, 896843, 449541, 639348,
747223, 832750, 182026, 460351, 337944, 354216, 528491, 177447, 223522, 438099,
906754, 992992, 512190, 369322, 613899, 897603, 288589, 383803, 679017, 97174,
320213, 59265, 64112, 769517, 138982, 902828, 426525, 951653, 848634, 786758,
121220, 287689, 165161, 885263, 597976, 261723, 683603, 864299, 57401, 530568,
662834, 269801, 986180}}
\meaning\z
\end{verbatim}

\edef\z{\QSfull {513653, 408866, 886204, 735578, 608552, 412004, 186578,
140974, 649711, 465136, 388683, 323362, 504730, 254715, 195793, 233621, 671299,
428170, 951423, 653603, 665197, 857787, 771700, 992045, 372838, 929992, 167911,
780076, 243286, 69869, 804743, 300412, 530086, 173893, 900738, 493815, 9980,
448301, 824577, 514010, 522537, 919250, 986196, 774531, 240895, 956406, 685109,
604079, 736896, 111898, 682533, 542445, 674548, 889917, 896843, 449541, 639348,
747223, 832750, 182026, 460351, 337944, 354216, 528491, 177447, 223522, 438099,
906754, 992992, 512190, 369322, 613899, 897603, 288589, 383803, 679017, 97174,
320213, 59265, 64112, 769517, 138982, 902828, 426525, 951653, 848634, 786758,
121220, 287689, 165161, 885263, 597976, 261723, 683603, 864299, 57401, 530568,
662834, 269801, 986180}}
\textcolor{blue}{\meaning\z}


+++\QSfull{}+++

\end{document}

Blockquote


code 4. No package needed, but limited to decimal numbers which one can compare with \ifdim.

\documentclass{article}
\usepackage{color}
\usepackage[straightquotes]{newtxtt}
\usepackage{xintkernel}

% THE QUICK SORT ALGORITHM EXPANDABLY
% adapted from xint.pdf user manual 
% to act on comma separated values.

% this variant uses no package whatsoever
% inputs must be comparable via \ifdim

\makeatletter
% defined here to avoid having to load xintkernel package
\long\def\xintdothis #1#2\xintorthat #3{\fi #1}%
\let\xintorthat \@firstofone
%
\makeatletter
% not needed for numerical inputs
% \catcode`! 3
% \catcode`? 3
\def\QSfull {\romannumeral0\qsfull }%
% first we check if empty list (else \qsfull@finish will not find a comma)
\def\qsfull   #1{\expandafter\qsfull@a\romannumeral-`0#1,!,?}%
\def\qsfull@a #1{\ifx,#1\expandafter\qsfull@abort\else
                        \expandafter\qsfull@start\fi #1}%
\def\qsfull@abort #1?{ }%
\def\qsfull@start {\expandafter\qsfull@finish\romannumeral0\qsfull@b,}%
\def\qsfull@finish ,#1{ #1}%
%
% we check if empty of single and if not pick up the first as Pivot:
\def\qsfull@b ,#1#2,#3{\ifx?#3\xintdothis\qsfull@empty\fi
                       \ifx!#3\xintdothis\qsfull@single\fi
                       \xintorthat \qsfull@separate {}{}{#1#2}#3}%
\def\qsfull@empty    #1#2#3#4{ }%
\def\qsfull@single   #1#2#3#4?{, #3}%
\def\qsfull@separate #1#2#3#4#5,%
{%
    \ifx!#4\expandafter\qsfull@separate@done\fi
    \ifdim #4#5pt>#3pt
         \expandafter\qsfull@separate@appendtogreater
    \else\expandafter\qsfull@separate@appendtosmaller
    \fi
          {#4#5}{#1}{#2}{#3}%
}%
%
\def\qsfull@separate@appendtogreater #1#2{\qsfull@separate {#2,#1}}%
\def\qsfull@separate@appendtosmaller #1#2#3{\qsfull@separate {#2}{#3,#1}}%
%
\def\qsfull@separate@done\ifdim #1%
    \expandafter\qsfull@separate@appendtogreater
    \else\expandafter\qsfull@separate@appendtosmaller\fi #2#3#4#5?%
{%
    \expandafter\qsfull@f\expandafter
    {\romannumeral0\qsfull@b #3,!,?}{\qsfull@b #4,!,?}{#5}%
}%
%
\def\qsfull@f #1#2#3{#2, #3#1}%
%
% \catcode`! 12
% \catcode`? 12
\makeatother


\begin{document}\thispagestyle{empty}\pagestyle{empty}
% EXAMPLE

\ttfamily

First example:

\edef\z {\QSfull {1.0, 0.5  ,0.3, 1.5  ,1.8,2.0,1.7, 0.4, 1.2, 1.4,
    1.3, 1.1, 0.7, 1.6, 0.6, 0.9, 0.8, 0.2  ,   0.1    ,1.9}}

1.0, 0.5  ,0.3, 1.5  ,1.8,2.0,1.7, 0.4, 1.2, 1.4,
    1.3, 1.1, 0.7, 1.6, 0.6, 0.9, 0.8, 0.2  ,   0.1    ,1.9

will give macro with meaning (notice that the output has the same extra spaces
after digits and before commas that the user may have left on input; this is a
feature, not a bug; on the other hand commas on output always are followed by a
space, again a feature).

\meaning\z

\def\a{3.14}
\def\b{3.11}
\def\c{3.2}
\def\d{3.09}
\expandafter\def\expandafter\z\expandafter{\romannumeral0\qsfull { \a, \b, \c, \d}}

\meaning\z


\bigskip
\clearpage
\bigskip

Example:
\begin{verbatim}
\oodef\z{\QSfull {513.653, 408.866, 886.204, 735.578, 608.552, 412.004,
186.578, 140.974, 649.711, 465.136, 388.683, 323.362, 504.730, 254.715,
195.793, 233.621, 671.299, 428.170, 951.423, 653.603, 665.197, 857.787,
771.700, 992.045, 372.838, 929.992, 167.911, 780.076, 243.286, 698.69,
804.743, 300.412, 530.086, 173.893, 900.738, 493.815, 9.980, 448.301, 824.577,
514.010, 522.537, 919.250, 986.196, 774.531, 240.895, 956.406, 685.109,
604.079, 736.896, 111.898, 682.533, 542.445, 674.548, 889.917, 896.843,
449.541, 639.348, 747.223, 832.750, 182.026, 460.351, 337.944, 354.216,
528.491, 177.447, 223.522, 438.099, 906.754, 992.992, 512.190, 369.322,
613.899, 897.603, 288.589, 383.803, 679.017, 97.174, 320.213, 592.65, 641.12,
769.517, 138.982, 902.828, 426.525, 951.653, 848.634, 786.758, 121.220,
287.689, 165.161, 885.263, 597.976, 261.723, 683.603, 864.299, 574.01,
530.568, 662.834, 269.801, 986.180}}
\meaning\z
\end{verbatim}

\oodef\z{\QSfull {513.653, 408.866, 886.204, 735.578, 608.552, 412.004,
186.578, 140.974, 649.711, 465.136, 388.683, 323.362, 504.730, 254.715,
195.793, 233.621, 671.299, 428.170, 951.423, 653.603, 665.197, 857.787,
771.700, 992.045, 372.838, 929.992, 167.911, 780.076, 243.286, 698.69,
804.743, 300.412, 530.086, 173.893, 900.738, 493.815, 9.980, 448.301, 824.577,
514.010, 522.537, 919.250, 986.196, 774.531, 240.895, 956.406, 685.109,
604.079, 736.896, 111.898, 682.533, 542.445, 674.548, 889.917, 896.843,
449.541, 639.348, 747.223, 832.750, 182.026, 460.351, 337.944, 354.216,
528.491, 177.447, 223.522, 438.099, 906.754, 992.992, 512.190, 369.322,
613.899, 897.603, 288.589, 383.803, 679.017, 97.174, 320.213, 592.65, 641.12,
769.517, 138.982, 902.828, 426.525, 951.653, 848.634, 786.758, 121.220,
287.689, 165.161, 885.263, 597.976, 261.723, 683.603, 864.299, 574.01,
530.568, 662.834, 269.801, 986.180}}
\textcolor{blue}{\meaning\z}

+++\QSfull{}+++

\end{document}

Blockquote


code 5. Again no package needed, this variant does alphabetical comparisons using \pdfstrcmp or XeTeX's \strcmp. This one requires an \edef but one could change it to act like the other ones. Blank items from the input are gobbled and do not make it to the output. The output has one space after each comma preceeding an item.

% COMPILE WITH XETEX (UTF8 file)

\documentclass{article}
\usepackage{color}
\usepackage[straightquotes]{newtxtt}
%\usepackage[french]{babel}% I tried to see if it impacted alphabetical
% sorting of é è etc... (no, even with french as class option)

% VARIANT FOR ALPHABETICAL INPUTS

% uses \pdfstrcmp from pdftex or \strcmp from xetex
% this variant only expands completely in an \edef 
% (full expansion of first token not enough).

% blank items are accepted and _discarded_.

% empty list (or list of only blank items) is also accepted and produces empty
% output.

\ifdefined\XeTeXinterchartoks
   \let\pdfstrcmp\strcmp
\else
   \usepackage[utf8]{inputenc}% for PDFLaTeX
\fi

\makeatletter
% defined here to avoid having to load xintkernel package
\long\def\xintdothis #1#2\xintorthat #3{\fi #1}%
\let\xintorthat \@firstofone
%
% use some (improbable) tokens as delimiters
\catcode`! 3
\catcode`? 3
\catcode`; 3
% first we check if empty list (else \qsfull@finish will not find a comma)

% Needs an \edef for expansion
% First we apply f-expansion to the argument to allow it to be a macro.
%
\def\QSfull #1{\expandafter\qsfull@a\romannumeral-`0#1,!,?}%
%
% first check if input has only blanks, or is empty
\def\qsfull@a #1{\ifx,#1\xintdothis\qsfull@a\fi
                 \ifx!#1\xintdothis\qsfull@abort\fi
                 \xintorthat{\qsfull@start #1}}%
\def\qsfull@abort #1?{}%
%
\def\qsfull@start {\expandafter\qsfull@finish\romannumeral0\qsfull@b,}%
\def\qsfull@finish ,#1{#1}% remove initial ,<space>

% We don't need to filter out case of blank first element, because it can
% never happen. The blanks are removed in the first pass and this first pass
% uses necessarily a non-blank pivot.

% We filter out case of empty or singleton list.

% The first item here can NOT be a blank, which would cause #1 to pick up a
% comma.

\def\qsfull@b ,#1#2,#3{\ifx?#3\xintdothis\qsfull@emptylist\fi
                       \ifx!#3\xintdothis\qsfull@singleton\fi
                       \xintorthat \qsfull@separate@a {}{}#1#2;#3}%
\def\qsfull@emptylist    #1?{}%
\def\qsfull@singleton    #1#2#3;!,?{, #3}%
%
\def\qsfull@separate@a  #1#2#3;#4#5,%
% first pass, remove blanks in passing.
% no need to be extra efficient for that.
{%
    \ifx,#4\expandafter\qsfull@valueisblank\fi
    \ifx!#4\expandafter\qsfull@separate@done\fi
    \if1\pdfstrcmp{#4#5}{#3}%
         \expandafter\qsfull@separate@a@appendtogreater
    \else\expandafter\qsfull@separate@a@appendtosmaller
    \fi
          #4#5?{#1}{#2}#3;%
}%
\def\qsfull@valueisblank \ifx#1\fi,#2?#3#4#5;{\qsfull@separate@a {#3}{#4}#5;#2,}%
\def\qsfull@separate@a@appendtogreater #1?#2{\qsfull@separate@a {#2, #1}}%
%
\def\qsfull@separate@a@appendtosmaller #1?#2#3{\qsfull@separate@a {#2}{#3, #1}}%
%
\def\qsfull@separate@done\if#1\fi #2?#3#4#5;?%
{%
    \qsfull@c #4,!,?, #5\qsfull@c #3,!,?%
}%
% Now that the first pass is done, there are no more blank items.
% In particular here.
\def\qsfull@c ,#1#2,#3{\ifx?#3\xintdothis\qsfull@emptylist\fi
                       \ifx!#3\xintdothis\qsfull@singleton\fi
                       \xintorthat \qsfull@separate {}{}#1#2;#3}%
%
\def\qsfull@separate  #1#2#3;#4#5,% blanks have already been filtered out.
{%
    \ifx!#4\expandafter\qsfull@separate@done\fi
    \if1\pdfstrcmp{#4#5}{#3}%
         \expandafter\qsfull@separate@a@appendtogreater
    \else\expandafter\qsfull@separate@a@appendtosmaller
    \fi
          #4#5?{#1}{#2}#3;%
}%
\def\qsfull@separate@appendtogreater #1?#2{\qsfull@separate {#2, #1}}%
\def\qsfull@separate@appendtosmaller #1?#2#3{\qsfull@separate {#2}{#3, #1}}%
%
%
\catcode`! 12
\catcode`? 12
\catcode`; 12
\makeatother


\begin{document}\thispagestyle{empty}\pagestyle{empty}
% EXAMPLE

\ttfamily

Example:

\edef\z{\QSfull{b,a}}
+++\z+++

\def\w {(notice , that , the , output , has , the , extra , space tokens,
  before , commas , from the input , , , , , , , , except, that, blank items,
  from the inputs, are, discarded, from the output, !!!!, this, is, a,
  feature, or, a, bug, ?,,,,,,,,,,, a,feature,naturally,., And,commas, in,
  output, always, are, followed, by, a, space, (, a,feature, which, can, be,
  easily, modified, in the code, ), , , , , , , , }


\edef\z{\QSfull\w}

\w\textcolor{green}{ENDOFINPUT}

becomes

\textcolor{blue}{\meaning\z}\textcolor{green}{ENDOFOUTPUT}


+++\QSfull{}+++

More reasonable example:

\def\w {Demain, dès l'aube, à l'heure où blanchit la campagne,
Je partirai. Vois-tu, je sais que tu m'attends.
J'irai par la forêt, j'irai par la montagne.
Je ne puis demeurer loin de toi plus longtemps.}

\edef\z{\QSfull\w}

\w

becomes

\textcolor{blue}{\meaning\z}

+++\QSfull{,}+++

Last example

\def\w {
    déraison,
    imprudence,
    erreur,
    fantaisie,
    frénésie,
    fièvre,
    écart,
    bêtise,
    emportement,
    vertige,
    imbécillité,
    chimère,
    connerie,
    passion,
    bizarrerie,
    loufoquerie,
    excès,
    caprice,
    marotte,
    égarement,
    hallucination,
    sottise,
    dérèglement,
    fêlure,
    extravagance,
    divagation,
    mode,
    fredaine,
    maladie mentale,
    névrose,
    dérangement,
    manie,
    imagination,
    insanité,
    humeur,
    lubie,
    aveuglement,
    trouble,
    aliénation,
    rage,
    idiotie,
    aberration,
    crétinisme,
    toquade,
    témérité,
    monstruosité,
    démence,
    dissipation,
    délire,
    psychose,
    saugrenuité,
    affolement,
    dépression,
    déséquilibre,
    frasque,
    obstination,
    absurdité}


\edef\z{\QSfull\w}

\w

becomes

\textcolor{blue}{\meaning\z}

+++\QSfull{,,}+++

\enlargethispage{\baselineskip}
I am surprised that ``é'' comes after all lowercase letters.
\end{document}

Blockquote


Code 6: Bottom-up Merge Sort using advanced techniques of expandable programming. Requires pdftex (or at least equivalent to \pdfescapestring). This code for decimal numbers acceptable by \ifdim. Can be extended to other comparison routines if desired.

\documentclass{article}
\usepackage{color}
\usepackage[straightquotes]{newtxtt}
\usepackage{xinttools}% NOT used by the code, only for inserting spaces after
                      % commas in ouput of \MergeSort in the example

\makeatletter
\def\MergeSort {\romannumeral0\mergesort }%
% The routine expects to manipulate explicit decimal numbers as acceptable
% by \ifdim tests.

% there are slightly faster techniques than the use of \ifx, \if conditionals
% in the macros below, but for the sake of legibility of the code, I wrote
% this draft using them nevertheless.

% WE EXPAND LIST ARGUMENT AND CHECK IF EMPTY
\def\mergesort #1{\expandafter\msort@a\romannumeral-`0#1,!,?,}%
\def\msort@a   #1{\ifx,#1\expandafter\msort@abort\else
                         \expandafter\msort@start\fi #1}%
\def\msort@abort #1?,{ }%
%
% FIRST BOTTOM-UP PASS, WE TAKE THIS OPPORTUNITY TO INSERT DELIMITERS
% and using \pdfescapestring trick to propagate expansion
% 
\def\msort@start {\expandafter\msort@c\pdfescapestring\bgroup\msort@b}%
\def\msort@b #1#2,#3#4,%
{%
    \ifx?#3\expandafter\msort@be\fi
    \ifx!#3\expandafter\msort@bs\fi
    \ifdim #1#2\p@>#3#4\p@
         \expandafter\@firstoftwo
    \else\expandafter\@secondoftwo
    \fi
    {#3#4,#1#2}{#1#2,#3#4},!,;\msort@b 
}%
\def\msort@be #1\msort@b {\iffalse{\fi}!;?;}%
\def\msort@bs \ifdim #1\p@#2\fi #3?,{#1\iffalse{\fi},!,;!;?;}%

% MERGING SUB-ROUTINE TO BE USED NEXT
% (improved: if first item of second bigger, keep it as long as necessary)
\def\msort@merge #1#2,#3;#4#5,%
{%
    \if!#1\expandafter\msort@merge@ea\fi
    \if!#4\expandafter\msort@merge@eb\fi
    \ifdim #1#2\p@>#4#5\p@ #4#5,%
       \expandafter\msort@merge
    \else\msort@merge@a #4#5%
    \fi #1#2,#3;%
}%
%
\def\msort@merge@ea #1\msort@merge@a #2\fi !,;{#2,}% possibly #2=!
\def\msort@merge@eb #1\fi #2;{#2}%
%
\def\msort@merge@a #1\fi #2,{\fi #2,\msort@merge@b #1,}%
\def\msort@merge@b #1,#2#3,%
{%
    \if!#2\expandafter\msort@merge@ea\fi
    \ifdim #2#3\p@>#1\p@ #1,%
         \expandafter\msort@merge
    \else\msort@merge@a #1%
    \fi #2#3,%
}%

% DO WE HAVE ONLY ONE LIST LEFT ? 
%    YES -> DONE
%     NO -> MERGE TWO AND KEEP GOING
\def\msort@c #1;#2#3;%
{%
    \if!#2\expandafter\msort@finish\fi
    \expandafter\msort@c
    \pdfescapestring\bgroup\msort@merge #1;#2#3;\msort@d 
}%

% KEEP ON FETCHING TWO BY TWO UNTIL HITTING FINAL ! OR ?
\def\msort@d #1#2;#3#4;%
{%
    \if?#3\expandafter\msort@de\fi
    \if!#3\expandafter\msort@ds\fi
    \msort@merge #1#2;#3#4;\msort@d 
}%
\def\msort@de #1\msort@d {\iffalse{\fi}!;?;}%
\def\msort@ds\msort@merge #1;#2?;{#1\iffalse{\fi};!;?;}%

% THIS IS FINAL CLEAN UP.
% THIS IS WHERE SPACES COULD GET REINSERTED AFTER COMMAS IF WANTED.
\def\msort@finish #1\msort@merge #2,!#3?;{ #2}%

\makeatother

\begin{document}\thispagestyle{empty}

+++\MergeSort {}+++

+++\MergeSort {1.1}+++

\MergeSort {1.2, 1.1, 1.3, 1.5, 0.9, 0.5}

\def\mylist{513.653, 408.866, 886.204, 735.578, 608.552, 412.004,
186.578, 140.974, 649.711, 465.136, 388.683, 323.362, 504.730, 254.715,
195.793, 233.621, 671.299, 428.170, 951.423, 653.603, 665.197, 857.787,
771.700, 992.045, 372.838, 929.992, 167.911, 780.076, 243.286, 698.69,
804.743, 300.412, 530.086, 173.893, 900.738, 493.815, 9.980, 448.301, 824.577,
514.010, 522.537, 919.250, 986.196, 774.531, 240.895, 956.406, 685.109,
604.079, 736.896, 111.898, 682.533, 542.445, 674.548, 889.917, 896.843,
449.541, 639.348, 747.223, 832.750, 182.026, 460.351, 337.944, 354.216,
528.491, 177.447, 223.522, 438.099, 906.754, 992.992, 512.190, 369.322,
613.899, 897.603, 288.589, 383.803, 679.017, 97.174, 320.213, 592.65, 641.12,
769.517, 138.982, 902.828, 426.525, 951.653, 848.634, 786.758, 121.220,
287.689, 165.161, 885.263, 597.976, 261.723, 683.603, 864.299, 574.01,
530.568, 662.834, 269.801, 986.180}

\expandafter\def\expandafter\z\expandafter{\romannumeral0\mergesort\mylist}

\show\z

With extra inserted spaces after commas before printing:

\textcolor{blue}{\xintListWithSep{, }{\xintCSVtoList{\MergeSort\mylist}}}

\end{document}

Blockquote

  • Using \pdfresettimer and \pdfelapsedtime for sorting 1000 random numbers I found that your macro is almost twice faster than mine. – Kpym Oct 15 '15 at 6:40
  • For 10000 random numbers : your qsort takes (on my laptop) 188 seconds, but my qsort never finish ... bravo ! – Kpym Oct 15 '15 at 7:15
  • 1
    @Manuel the only thing to be really aware of is that TeX does not discard space tokens after control sequences of the type \1, \2 (non-letter one character cs). I am also aware of this: if TeX expands \test X at top level, and if \test macro itself makes the space active, then the space between \test and X will be active. It is not swallowed with TeX gathering the \test control sequence. – user4686 Oct 15 '15 at 22:39
  • 1
    What a wonderful answer! – Gonzalo Medina Oct 17 '15 at 18:03
  • The \msort@b should not use \@firstoftwo/\@secondoftwo, but put directly #1#2,#3#4 or #3#4,#1#2 but I have edited too many times already my answer. The main speed bottleneck is in the merge operation: this can be made faster by fetching more items of the second list; but controlling the endings become more complicated. At least a 2x additional gain could I think be obtained with such ideas, but the code becomes more involved. – user4686 Oct 24 '15 at 21:45
10

A short demo using l3sort:

\documentclass{article}
\usepackage{expl3,l3sort,xparse}
\ExplSyntaxOn
\cs_set:Npn \quicksort_fp:nnTF #1#2
  { \fp_compare:nNnTF {#2} > {#1} }
\DeclareExpandableDocumentCommand \quicksort { m }
  { \tl_sort:nN {#1} \quicksort_fp:nnTF }
\ExplSyntaxOff
\edef\demo
  {%
    \quicksort
      {%
        {1.0}{0.5}{0.3}{1.5}{1.8}{2.0}{1.7}{0.4}{1.2}{1.4}
        {1.3}{1.1}{0.7}{1.6}{0.6}{0.9}{0.8}{0.2}{0.1}{1.9}
     }%
 }
\show\demo

At present, the code here is somewhat experimental and in particular only the generic tl sort is expandable. That could be extended to comma lists or similar if required.

  • does it do individual comparisons with \ifdim ? – user4686 Oct 17 '15 at 18:09
  • @jfbu Not here: we are comparing fp not dim data, so the FPU is used – Joseph Wright Oct 17 '15 at 18:15
  • ah ok. I suppose there is also a variant for alphabetical ordering ? – user4686 Oct 17 '15 at 18:26
  • @jfbu Alphabetical is a lot more complex (Unicode ordering rules, ...): at present I'd go with a wrapper around \pdfstrcmp, at least if sorting in the ASCII range. – Joseph Wright Oct 17 '15 at 18:29
  • @JosephWright So quicksort_fp is expandable, nice ! When you say "That could be extended to comma lists or similar if required.", does this means that there is simple option or I have to use a particular CSV parser ? – Kpym Oct 17 '15 at 18:56
6

This algorithm uses the median of the first, middle and last element for the pivot. I tried to minimize conversions between text and numbers, assuming that \csname is faster than \strip@pt. (With all the \expandafters needed I wonder if this is really true.)

The first step is to parse the array stored as a comma delimited string (in other words, a tikz array) and convert it to a global \csname array of the form \QSarray1, \QSarray2, ... . This is what is used by the recursive macro \quicksort{low}{high}. Finally the sorted array is converted back into a comma delimited string.

Since leading blanks do not seem to affect the sorting, the best place to remove them is in the output stage (using \ignorespaces). This may however adversely affect additional processing.

It occurred to me that there are going to be a LOT of blocks of 3 or less to sort, so I streamlined the code for those cases. I discovered that while there are generally few entries equal to the pivot, in certain cases removing the pivot from further sorts is the ONLY progress made.

\documentclass{article}

\let\END=\eof% almost anything will do

\def\qsort#1#2% #1 = input array of decimal numbers, #2 = macro name for sorted output array
{\bgroup% assign resisters for all routines
  \countdef\QStotal=1
  \countdef\QSindex=2
  \countdef\QSlow=3
  \countdef\QShigh=4
  \countdef\QSmiddle=5
%
  \dimendef\QSpivot=0
  \dimendef\QStest=1
  \dimendef\QSalt=2
% parse comma delimited data and store in QSarray1, QSarray2, ..
  \QStotal=0
  \expandafter\parseCSV\detokenize #1,\END,\relax

% sort QSarray
  \quicksort{1}{\the\QStotal}%
% create output array (string)
  \QSindex=1
  \edef\QStemp{\ignorespaces\csname QSarray1\endcsname}%
  \global\expandafter\let\csname QSarray1\endcsname=\relax
  \loop\advance\QSindex by 1
    \edef\QStemp{\QStemp,\ignorespaces\csname QSarray\the\QSindex\endcsname}%
    \global\expandafter\let\csname QSarray\the\QSindex\endcsname=\relax% clear space
    \ifnum\QSindex<\QStotal \repeat
  \xdef#2{\QStemp}%
\egroup}

\def\parseCSV #1,{\ifx\END#1\relax\else
  \advance\QStotal by 1
  \expandafter\xdef\csname QSarray\the\QStotal\endcsname{#1}%
  \expandafter\parseCSV\fi}

\newcommand{\quicksort}[2]% #1 = low index, %2 = high index
{\bgroup% use local variables
  \edef\plow{#1}
  \edef\phigh{#2}
  \QSindex=\numexpr \phigh-\plow+1\relax
  \ifnum\QSindex>1
    \ifnum\QSindex=2 \QSortTwo
    \else
      \ifnum\QSindex=3 \QSortThree
      \else \QSortN
      \fi
    \fi
  \fi
\egroup}

\newcommand{\QSortN}{% use median of first, last, and middle for pivot
  \QSmiddle=\numexpr \plow+\QSindex/2\relax
  \edef\pmiddle{\the\QSmiddle}
  \QStest=\csname QSarray\plow\endcsname pt
  \QSpivot=\csname QSarray\pmiddle\endcsname pt
  \QSalt=\csname QSarray\phigh\endcsname pt
  \ifdim\QStest<\QSpivot
    \ifdim\QSpivot<\QSalt %\QSpivot=\QSpivot
    \else
      \ifdim\QStest<\QSalt \QSpivot=\QSalt
        \let\pmiddle=\phigh
      \else \QSpivot=\QStest
        \let\pmiddle=\plow
      \fi
    \fi
  \else
    \ifdim\QStest<\QSalt \QSpivot=\QStest
      \let\pmiddle=\plow
    \else
      \ifdim\QSpivot<\QSalt \QSpivot=\QSalt
      \let\pmiddle=\phigh
      \fi
    \fi
  \fi
  \expandafter\let\expandafter\pmiddle\csname QSarray\pmiddle\endcsname
% separate into \QSlow1, \QSlow2, ... and \QShigh1, \QShigh2, ...
  \QSlow=0
  \QSmiddle=0
  \QShigh=0
  \QSindex=\plow\relax
  \loop
    \expandafter\let\expandafter\temp\csname QSarray\the\QSindex\endcsname
    \QStest=\temp pt
    \ifdim\QStest<\QSpivot
      \advance\QSlow by 1
      \expandafter\let\csname low\the\QSlow\endcsname=\temp
    \else
      \ifdim\QStest>\QSpivot
        \advance\QShigh by 1
        \expandafter\let\csname high\the\QShigh\endcsname=\temp
      \else
        \advance\QSmiddle by 1
      \fi
    \fi
    \advance\QSindex by 1
  \ifnum\QSindex>\phigh\relax\else\repeat
% put low and high values (pointers) back into QSarray
  \QSindex=\plow
  \loop\ifnum\QSlow>0
    \expandafter\let\expandafter\temp\csname low\the\QSlow\endcsname
    \global\expandafter\let\csname QSarray\the\QSindex\endcsname=\temp
    \advance\QSindex by 1
    \advance\QSlow by -1
  \repeat
  \QSlow=\numexpr \QSindex-1\relax
  \edef\highestlow{\the\QSlow}
  \loop\ifnum\QSmiddle>0
    \global\expandafter\let\csname QSarray\the\QSindex\endcsname=\pmiddle
    \advance\QSindex by 1
    \advance\QSmiddle by -1
  \repeat
  \edef\lowesthigh{\the\QSindex}
  \loop\ifnum\QShigh>0
    \expandafter\let\expandafter\temp\csname high\the\QShigh\endcsname
    \global\expandafter\let\csname QSarray\the\QSindex\endcsname=\temp
    \advance\QSindex by 1
    \advance\QShigh by -1
  \repeat
% sort low and high values separately
  \quicksort{\plow}{\highestlow}%
  \quicksort{\lowesthigh}{\phigh}%
}

\newcommand{\QSortTwo}{% called frequently
  \expandafter\let\expandafter\tempa\csname QSarray\plow\endcsname
  \expandafter\let\expandafter\tempb\csname QSarray\phigh\endcsname
  \QStest=\tempa pt
  \QSalt=\tempb pt
  \ifdim\QStest>\QSalt
    \global\expandafter\let\csname QSarray\plow\endcsname=\tempb
    \global\expandafter\let\csname QSarray\phigh\endcsname=\tempa
  \fi}

\newcommand{\QSortThree}{% three way swap
  \QSmiddle=\numexpr \plow+1\relax
  \edef\pmiddle{\the\QSmiddle}
  \expandafter\let\expandafter\tempa\csname QSarray\plow\endcsname
  \expandafter\let\expandafter\tempb\csname QSarray\pmiddle\endcsname
  \expandafter\let\expandafter\tempc\csname QSarray\phigh\endcsname
  \QStest=\tempa pt
  \QSpivot=\tempb pt
  \QSalt=\tempc pt
  \ifdim\QStest<\QSpivot
    \ifdim\QSpivot<\QSalt% test < pivot < alt
    \else
      \global\expandafter\let\csname QSarray\phigh\endcsname=\tempb
      \ifdim\QStest<\QSalt% test < alt < pivot
        \global\expandafter\let\csname QSarray\pmiddle\endcsname=\tempc
      \else% alt < test < pivot
        \global\expandafter\let\csname QSarray\plow\endcsname=\tempc
        \global\expandafter\let\csname QSarray\pmiddle\endcsname=\tempa
      \fi
    \fi
  \else
    \ifdim\QSpivot<\QSalt
      \global\expandafter\let\csname QSarray\plow\endcsname=\tempb
      \ifdim\QStest<\QSalt% pivot < test < alt
        \global\expandafter\let\csname QSarray\pmiddle\endcsname=\tempa
      \else% pivot < alt < test
        \global\expandafter\let\csname QSarray\pmiddle\endcsname=\tempc
        \global\expandafter\let\csname QSarray\phigh\endcsname=\tempa
      \fi
    \else% alt < pivot < test
      \global\expandafter\let\csname QSarray\plow\endcsname=\tempc
      \global\expandafter\let\csname QSarray\phigh\endcsname=\tempa
    \fi
  \fi}

\begin{document}

\edef\test{{1,10,2,9,3,8,4,7,5,6}}% tikz array

\qsort{\test}{\result}
\result

\end{document}

Personally, I could care less about making things expandable. Since then I best I've been able to find is:

\def\bar{\edef\test{TEST}\test}
\edef\foo{\noexpand\bar}
\foo
(\meaning\foo)

\def\foo{\bar}
\foo
(\meaning\foo)

In any case, to get the data out of the \bgroup...\egroup you are going to need a global macro anyway, so why not use it for the output?

OTOH, I was curious about the quick sort routine, which I had never previously implemented. It is not, however, the fastest sort routine. A self-balancing binary tree does N log N for ALL data sets.

\documentclass{article}

\let\END=\eof% almost anything will do

% returns sorted data in \QSresult
% global arrays: \QSdata, \QSlow, \QShigh, \QSmiddle, \QSlowindex and \QShighindex

\newcommand*{\qsort}[1]% #1 = input array of decimal numbers
{\bgroup% assign resisters for all routines
  \countdef\QStotal=1
  \countdef\QSindex=2
  \countdef\QSlow=3
  \countdef\QShigh=4
  \countdef\QSmiddle=5
%
  \dimendef\QSvalue=0
  \dimendef\QStest=1
% parse comma delimited data and store in QSarray1, QSarray2, ..
  \QStotal=0
  \expandafter\parseCSV\detokenize #1,\END,\relax
% after this point name conflicts no longer matter
% build tree
  \QSindex=0
  \QScreate
  \edef\start{1}%
  \loop\ifnum\QSindex<\QStotal
    \QScreate
    \QStest=\csname QSdata\theindex\endcsname pt\relax
    \QSpivot{\start}%
    \let\start=\QSresult
  \repeat
% create output array (string)
  \QSindex=0
  \QSsearch{\start}%
  \edef\temp{\QSresult}%
  \advance\QSindex by 1
  \loop
    \QSsearch{\start}%
    \edef\temp{\temp,\QSresult}%
    \advance\QSindex by 1
  \ifnum\QSindex<\QStotal \repeat
  \global\let\QSresult=\temp%
% clean up
  \QSindex=0
  \loop\QSdestroy
  \ifnum\QSindex<\QStotal \repeat
\egroup}

\def\parseCSV #1,{\ifx\END#1\relax\else
  \advance\QStotal by 1
  \expandafter\xdef\csname QSdata\the\QStotal\endcsname{#1}%
  \expandafter\parseCSV\fi}

\newcommand*{\QScreate}{% initialize data structure
  \advance\QSindex by 1
  \edef\theindex{\the\QSindex}%
  \expandafter\xdef\csname QSlow\theindex\endcsname{0}%
  \expandafter\xdef\csname QShigh\theindex\endcsname{0}%
  \expandafter\xdef\csname QSmiddle\theindex\endcsname{1}%
  \expandafter\xdef\csname QSlowindex\theindex\endcsname{}%
  \expandafter\xdef\csname QShighindex\theindex\endcsname{}%
}
\newcommand*{\QSdestroy}{% reset everything to \relax
  \advance\QSindex by 1
  \edef\theindex{\the\QSindex}%
  \global\expandafter\let\csname QSdata\theindex\endcsname=\relax
  \global\expandafter\let\csname QSlow\theindex\endcsname=\relax
  \global\expandafter\let\csname QShigh\theindex\endcsname=\relax
  \global\expandafter\let\csname QSmiddle\theindex\endcsname=\relax
  \global\expandafter\let\csname QSlowindex\theindex\endcsname=\relax
  \global\expandafter\let\csname QShighindex\theindex\endcsname=\relax
}
\newcommand*{\QSnopivot}[1]% #1 = tree index
{\bgroup% use local values
  \edef\start{#1}%
  \QSvalue=\csname QSdata\start\endcsname pt\relax
  \ifdim\QStest<\QSvalue
    \QSlow=\csname QSlow\start\endcsname\relax
    \ifnum\QSlow=0\relax
      \expandafter\xdef\csname QSlowindex\start\endcsname{\theindex}%
      \expandafter\xdef\csname QSlow\start\endcsname{1}%
    \else
      \advance\QSlow by 1
      \expandafter\xdef\csname QSlow\start\endcsname{\the\QSlow}%
      \expandafter\QSpivot{\csname QSlowindex\start\endcsname}%
      \global\expandafter\let\csname QSlowindex\start\endcsname=\QSresult%
    \fi
  \else
    \ifdim\QStest>\QSvalue
      \QShigh=\csname QShigh\start\endcsname\relax
      \ifnum\QShigh=0\relax
        \expandafter\xdef\csname QShighindex\start\endcsname{\theindex}%
        \expandafter\xdef\csname QShigh\start\endcsname{1}%
      \else
        \advance\QShigh by 1
        \expandafter\xdef\csname QShigh\start\endcsname{\the\QShigh}%
        \expandafter\QSpivot{\csname QShighindex\start\endcsname}%
        \global\expandafter\let\csname QShighindex\start\endcsname=\QSresult%
      \fi
    \else
      \QSmiddle=\csname QSmiddle\start\endcsname\relax
      \advance\QSmiddle by 1
      \expandafter\xdef\csname QSmiddle\start\endcsname{\the\QSmiddle}%
    \fi
  \fi
\egroup}
% returns (revised) tree index in \QSresult
\newcommand{\QSpivot}[1]% #1 = tree index
{\bgroup% use local values
  \edef\start{#1}%
  \QSlow=\csname QSlow\start\endcsname\relax
  \QShigh=\csname QShigh\start\endcsname\relax
  \QSmiddle=\csname QSmiddle\start\endcsname\relax
  \QSvalue=\csname QSdata\start\endcsname pt\relax
  \ifdim\QStest<\QSvalue
    \ifnum\QSlow=0
      \expandafter\xdef\csname QSlowindex\start\endcsname{\theindex}%
      \expandafter\xdef\csname QSlow\start\endcsname{1}%
      \global\let\QSresult=\start
    \else
      \ifnum\QSlow>\QShigh% pivot low
        \expandafter\let\expandafter\next\csname QSlowindex\start\endcsname
        \expandafter\let\expandafter\after\csname QShighindex\next\endcsname
        \QSlow=\csname QShigh\next\endcsname
        \expandafter\xdef\csname QSlow\start\endcsname{\the\QSlow}%
        \expandafter\xdef\csname QSlowindex\start\endcsname{\after}%
        \advance\QShigh by \QSlow
        \advance\QShigh by \QSmiddle
        \expandafter\xdef\csname QShigh\next\endcsname{\the\QShigh}%
        \expandafter\xdef\csname QShighindex\next\endcsname{\start}%
        \QSnopivot{\next}%
        \global\let\QSresult=\next%
      \else
        \advance\QSlow by 1
        \expandafter\xdef\csname QSlow\start\endcsname{\the\QSlow}%
        \expandafter\QSpivot{\csname QSlowindex\start\endcsname}%
        \global\expandafter\let\csname QSlowindex\start\endcsname=\QSresult%
        \global\let\QSresult=\start%
      \fi% end of \QSlow > \QShigh
    \fi% end of \QSlow = 0
  \else
    \ifdim\QStest>\QSvalue
      \ifnum\QShigh=0\relax
        \expandafter\xdef\csname QShighindex\start\endcsname{\theindex}%
        \expandafter\xdef\csname QShigh\start\endcsname{1}%
        \global\let\QSresult=\start%
      \else
        \ifnum \QShigh>\QSlow% pivot high
          \expandafter\let\expandafter\next\csname QShighindex\start\endcsname
          \expandafter\let\expandafter\after\csname QSlowindex\next\endcsname
          \QShigh=\csname QSlow\next\endcsname
          \expandafter\xdef\csname QShigh\start\endcsname{\the\QShigh}%
          \expandafter\xdef\csname QShighindex\start\endcsname{\after}%
          \advance\QSlow by \QShigh
          \advance\QSlow by \QSmiddle
          \expandafter\xdef\csname QSlow\next\endcsname{\the\QSlow}%
          \expandafter\xdef\csname QSlowindex\next\endcsname{\start}%
          \QSnopivot{\next}%
          \global\let\QSresult=\next
        \else
          \advance\QShigh by 1
          \expandafter\xdef\csname QShigh\start\endcsname{\the\QShigh}%
          \expandafter\QSpivot{\csname QShighindex\start\endcsname}%
          \global\expandafter\let\csname QShighindex\start\endcsname=\QSresult%
          \global\let\QSresult=\start%
        \fi% end of \QShigh > \QSlow
      \fi% end of \QShigh = 0
    \else
      \advance\QSmiddle by 1
      \expandafter\xdef\csname QSmiddle\start\endcsname{\the\QSmiddle}%
      \global\let\QSresult=\start%
    \fi% end of \QStest > \QSvalue
  \fi% end of \QStest < value
\egroup}
% return data in \QSresult
\newcommand*{\QSsearch}[1]% #1 = start of tree
{\bgroup
  \edef\start{#1}%
  \QSlow=\csname QSlow\start\endcsname\relax
  \ifnum\QSindex<\QSlow
    \expandafter\let\expandafter\next\csname QSlowindex\start\endcsname
    \QSsearch{\next}%
  \else
    \advance\QSindex by -\QSlow
    \QSmiddle=\csname QSmiddle\start\endcsname\relax
    \ifnum\QSindex<\QSmiddle
      \global\expandafter\let\expandafter\QSresult\csname QSdata\start\endcsname
    \else
      \advance\QSindex by -\QSmiddle
      \expandafter\let\expandafter\next\csname QShighindex\start\endcsname
      \QSsearch{\next}%
    \fi
  \fi
\egroup}

\begin{document}

\edef\test{{1,10,2,9,3,8,4,7,5,6}}% tikz array

\qsort{\test}
\QSresult

\end{document}
  • +1 Thanks for the nice code, not using any library (I appreciate this). But unfortunately your qsort is not expandable (it use many edef, xdef, ... inside). My original code is not expandable too, but I can easily modify it to take two arguments and to store the result in the second one. – Kpym Oct 17 '15 at 6:21
  • There is a bug : try {1,1,2} :( – Kpym Oct 17 '15 at 6:33
  • @jfbu this is not an identical values problem : {1,11} fails too, and many others ... – Kpym Oct 17 '15 at 8:01
  • @Kpym - I fixed the parser, I think. At least it can handle {1,11} now. – John Kormylo Oct 17 '15 at 23:55
  • @JohnKormylo thank for your efforts! Sorry to announce you that the parsing is not working well ; {1,1,2,1} is failing. May be you can use only the parsing part of @jfbu's implementation ? – Kpym Oct 18 '15 at 5:33
2

Using lambda.sty (for fun)

The lambda.sty package define fully expandables conditionnals and lists. In a similar way, the following macros define binary trees and a \BSTSort macro which can tree-sort a lambda list. It is not exactly quicksort, but is very similar.

\documentclass{article}

\usepackage{lambda}

\makeatletter
% Tree Data type (Similar to list)
\def\Branch#1#2#3#4#5{#4{#1}{#2}{#3}}
\def\Pousse#1{\Branch{#1}\Nil\Nil} % Leaf

% In-order traversal of a tree
\def\ListTree#1{#1\ListTree@{\Nil}}
\def\ListTree@#1#2#3{\Cat{\ListTree{#2}}{\Cons{#1}{\ListTree{#3}}}}

% Insert elem #2 in tree #3 according to sorting #1
\def\InsertTree#1#2#3{#3{\InsertTree@{#1}{#2}}{\Pousse{#2}}} 
\def\InsertTree@#1#2#3#4#5{#1{#2}{#3}%
  {\Branch{#3}{\InsertTree{#1}{#2}{#4}}{#5}}% Inserted element is less than root
  {\Branch{#3}{#4}{\InsertTree{#1}{#2}{#5}}}% Inserted element is more than root
}

\def\BST#1{\Foldr{\InsertTree#1}\Nil} % Builds BST with order #1

\def\BSTSort#1{\Compose\ListTree{\BST{#1}}} % Tree-sort
\makeatother

\begin{document}
% See the lambda-list documentation for \Listize and \Unlistize
\edef\z{\Unlistize{\BSTSort\Lessthan{\Listize[3,2,8,1,2,7,4,1,3,4]}}}
\meaning\z
\end{document}

Note that \BSTSort is quite a bit faster than the \Insersort provided with the lambda package.

EDIT: As noted, the lambda-supplied \Lessthan macro only compares integers. It is easy to define other orders. For instance, declare the following real-compare order:

\def\LessthanReal#1#2{\TeXif{\ifdim#1pt<#2pt }}

Then you can use \BSTSort\LessthanReal\li to sort the list \li.

  • Very interesting ! But It seems that it works only for list on integers. Could it be changed to accept reals ? – Kpym Oct 27 '15 at 17:33
  • @Kpym See the edit. – TonioElGringo Oct 28 '15 at 8:34
  • That is perfect, thanks. I've done some tests, and the maximal length of the list seems to be around 720 numbers. I've done also some speed comparisons, using \pdfresettimer-\pdfelapsedtime, with @jfbu's algorithme 4 and lambda sort is around 10 times slower (and 3 times slower than l3sort), which is better than my original sort ;) – Kpym Oct 28 '15 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.