9

I have a clist that I'd like to bubble sort. I'm sure this is a simple matter of something like \clist_bubblesort:N or something, but I don't know what the appropriate incantation is. A quick google didn't reveal anything obvious...

13

The l3sort package does that (but currently with a merge sort, I hope you don't mind the speed-up), as long as the clist has at most 20000 items or so (I can't remember the exact limit).

\documentclass{article}
\usepackage{expl3, xparse}
\ExplSyntaxOn
\clist_new:N \l_my_clist
\NewDocumentCommand{\sorted}{m}
  {
    \clist_set:Nn \l_my_clist {#1}
    \clist_sort:Nn \l_my_clist
      { \int_compare:nTF { ##1 > ##2 } { \sort_return_swapped: } { \sort_return_same: } }
    \clist_use:Nnnn \l_my_clist { ~ and ~ } { , ~ } { , ~ and ~ }
  }
\ExplSyntaxOff
\begin{document}
  The sorted numbers are \sorted{3, 4, 123, -1, 2, -01}.
\end{document}

The command stores the given list in a clist variable, \l_my_clist, then sorts it, using the following criterion: compare two items as integers; if the first is greater than the second, they must be swapped; otherwise keep them in the same order. Then use that clist, with the appropriate separators: ~and~ for lists with two items, ,~ between most items, ending with ,~and~. The ~ are in fact space tokens since space is ignored.

Note that the sort is stable, in the sense that numbers that compare equal are considered ordered (this relies, of course, on choosing the test appropriately, calling \sort_return_same: when the numbers are equal, as is done here).

I have a longer term plan to provide something like \sort_keep_one:n {##1} which would allow to keep only one of the two terms, which is useful to remove duplicates. I can imagine this being useful too when building an index, keeping only one copy of each work, but keeping track of a list of page numbers: \sort_keep_one:n { ##1 ~ <pages> }.

  • 4
    We should probably finalise this module, if we can: it's a useful and general idea, needing only a good interface discussion. – Joseph Wright May 8 '13 at 12:47
  • @JosephWright I agree. On my side I need to unearth some code that would let us have this \sort_keep_one:n functionality, as the current approach with merge sort makes it impossible. – Bruno Le Floch May 8 '13 at 12:59
  • That's an implementation thing, right? If so, we should take about interface on the LaTeX-L list and get that sorted ;-) – Joseph Wright May 8 '13 at 13:08
  • Yes, but it is important to know what is feasible/not (so my main point was "there exists an efficient implementation where it is possible to reduce the number of items in the list"). Let's. – Bruno Le Floch May 8 '13 at 13:50
  • 3
    Maybe this answer should be updated to the current state of expl3 (other commands for returning the state, not experimental, but in official interface3 and maybe an update on the \sort_keep_one stuff). – TeXnician Apr 5 '18 at 8:47

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.