References: <4F32E78F.6070903@morningstar2.co.uk>
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="huq684BweRXVnRxX"
Content-Disposition: inline
User-Agent: Mutt/1.5.21 (2010-09-15)
Message-ID:  <20120209143214.GA13913@csmvddesktop>
Date:         Thu, 9 Feb 2012 14:32:14 +0000
Reply-To: Mailing list for the LaTeX3 project
              <LATEX-L@listserv.uni-heidelberg.de>
Sender: Mailing list for the LaTeX3 project <LATEX-L@listserv.uni-heidelberg.de>
From: dongen <dongen@CS.UCC.IE>
Subject: Re: Deprecated functions: \prg_quicksort: family
To: LATEX-L@listserv.uni-heidelberg.de
In-Reply-To:  <4F32E78F.6070903@morningstar2.co.uk>
Precedence: list
Status: R

--huq684BweRXVnRxX
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline

* Joseph Wright <joseph.wright@MORNINGSTAR2.CO.UK> [2012-02-08 21:22:23 +0000]:

Hi Joseph,

: The \prg_quicksort: family of functions have been deprecated, and will
: be removed from l3kernel on or before 2012-05-31.
: 
: Non-expandable but clearer functions are available in the experimental
: l3sorrt, recently added to the LaTeX3 CTAN bundle.

I'm attaching a clear and (unless I'm missing something) an expandable
version of quicksort.

I started implementing it when I saw your email. It was good fun.
The actual definition takes 24 lines. The implementation is not
stable. Please feel free to use/adapt/bin/etc.

Regards,


Marc van Dongen

--huq684BweRXVnRxX
Content-Type: text/x-tex; charset=us-ascii
Content-Disposition: attachment; filename="qsort.tex"

\documentclass{article}

\usepackage{xparse}
\usepackage{l3int}
\usepackage{l3tl}

\ExplSyntaxOn

\DeclareDocumentCommand\qsort{ m }{
    \qs_try:o [#1,]
}

\cs_new_nopar:Npn \qs_try:o[#1,#2]{%
    \tl_if_empty:nTF{#1}
        {}
        {\qs_try_partition:onoo [#2] {#1} [,] [,]}
}

% [#1] is the remainder of the list
% #2   is the partition criterion
% [#3] are the members less that the partition criterion
% [#4] are the members greater than or equal to the partition criterion
\cs_new_nopar:Npn \qs_try_partition:onoo [#1]#2[#3][#4]{
    \tl_if_empty:nTF {#1}
        {\qs_recursive_sort:noo {#2} [#3] [#4]}
        {\qs_partition:onoo [#1]#2[#3][#4]}
}

% [#1,#2] is the remainder of the list
% #3   is the partition criterion
% [#4] are the members less that the partition criterion
% [#5] are the members greater than or equal to the partition criterion
\cs_new_nopar:Npn \qs_partition:onoo [#1,#2]#3[#4][#5]{
    \int_compare:nNnTF
       {#3} > {#1}
       {\qs_try_partition:onoo [#2]#3[,#1#4][#5]}
       {\qs_try_partition:onoo [#2]#3[#4][,#1#5]}
}

% #1 is the partition criterion
% #2 are the members less that the partition criterion
% #3 are the members greater than or equal to the partition criterion
\cs_new_nopar:Npn \qs_recursive_sort:noo #1[#2,#3][#4,#5]{
    \tl_if_empty:nTF{#3}{}{\qs_try:o [#3],}
    #1
    \tl_if_empty:nTF{#5}{}{,\qs_try:o [#5]}
}

\ExplSyntaxOff

\begin{document}

\qsort{1,9,2,3,8,8,6,8,9,0,5,9,4,7,1,2,7,8,9,8,9,1,2,8,1,1,8,5,3,4,8,9,2,5,1,8,9,2,5,1,%
1,9,2,3,8,8,6,8,9,0,5,9,4,7,1,2,7,8,9,8,9,1,2,8,1,1,8,5,3,4,8,9,2,5,1,8,9,2,5,1,%
1,9,2,3,8,8,6,8,9,0,5,9,4,7,1,2,7,8,9,8,9,1,2,8,1,1,8,5,3,4,8,9,2,5,1,8,9,2,5,1,%
1,9,2,3,8,8,6,8,9,0,5,9,4,7,1,2,7,8,9,8,9,1,2,8,1,1,8,5,3,4,8,9,2,5,1,8,9,2,5,1,%
1,9,2,3,8,8,6,8,9,0,5,9,4,7,1,2,7,8,9,8,9,1,2,8,1,1,8,5,3,4,8,9,2,5,1,8,9,2,5,1,%
1,9,2,3,8,8,6,8,9,0,5,9,4,7,1,2,7,8,9,8,9,1,2,8,1,1,8,5,3,4,8,9,2,5,1,8,9,2,5,1,%
1,9,2,3,8,8,6,8,9,0,5,9,4,7,1,2,7,8,9,8,9,1,2,8,1,1,8,5,3,4,8,9,2,5,1,8,9,2,5,1,-1,%
1,9,2,3,8,8,6,8,9,0,5,9,4,7,1,2,7,8,9,8,9,1,2,8,1,1,8,5,3,4,8,9,2,5,1,8,9,2,5,1,%
1,9,2,3,8,8,6,8,9,0,5,9,4,7,1,2,7,8,9,8,9,1,2,8,1,1,8,5,3,4,8,9,2,5,1,8,9,2,5,1,%
1,9,2,3,8,8,6,8,9,0,5,9,4,7,1,2,7,8,9,8,9,1,2,8,1,1,8,5,3,4,8,9,2,5,1,8,9,2,5,1,%
1,9,2,3,8,8,6,8,9,0,5,9,4,7,1,2,7,8,9,8,9,1,2,8,1,1,8,5,3,4,8,9,2,5,1,8,9,2,5,1}


\end{document}

--huq684BweRXVnRxX--