How to sort an alphanumeric list

Question

I have been trying to find a package or a method to sort lists of names in an easy manner in TeX/LaTeX. I have tried some of the routines in the xfor package, as well as looked at some of the new macros in LaTeX3 but was not very successful with either of them.

I have come with the idea of using the MakeIndex program to sort and categorize. It is available with every distribution and the LaTeX class is very short and easily hackable being approximately 36 lines long (including the glossary macros that I can eliminate) and a few more definitions for styling in the basic book or article class.

Here is a minimal example that sorts a list of names by profession (category).

\documentclass[11pt]{article}
\usepackage{makeidx}
\def\addName#1#2{\index{Name!#1}\index{#2!#1}}
\makeindex
\begin{document}
\renewcommand{\indexname}{Famous and Infamous Sorted People}
\addName{Leslie Lamport}{Computer Scientist} 
\addName{Donald Knuth}{Computer Scientist}
\addName{Tim Berners Lee}{Computer Scientist}
\addName{Brian Kernighan}{Computer Scientist}
\addName{Noam Chomsky}{Linguist}
\addName{Yiannis Lazarides}{Lifelong Trainee \protect\TeX nician}
\addName{Leonard Euler}{Mathematician}
\addName{Carl Friendrich Gauss}{Mathematician}
\addName{August Ferdinard M\"{o}bius}{Mathematician}

%% Importing the .ind file rather than use \printindex
%% so we do not need to redefine the command
%% 
\input{indextest.ind}

\begin{verbatim}
\begin{theindex}
\item Lifelong Trainee \TeX nician
    \subitem Yiannis Lazarides, 1
  \item Linguist
    \subitem Noam Chomsky, 1 
\end{theindex}
\end{verbatim}
\end{document}

Is this a good idea? Are there any packages devoted to alphanumeric sorting? I know it can easily be done with an external script, but I am looking for a TeX/LaTeX solution. Do you think it is a good approach?

Answer 1

I didn't look at Charles's code because I wanted to see how difficult it would be to implement a generic sorting macro that was expandable. It turns out that it's more or less straight-forward to do in a continuation-passing style.

\documentclass{article}
\usepackage{etoolbox}
\makeatletter
% #1 - comparator
% #2 - token list to sort
\newcommand\sort[2]{%
        \ifstrempty{#2}
        {}% else
        {%
                \sort@begin#1{}#2\sort@s\sort@begin
        }%
}

% helpers
\def\sort@s{\sort@s}
\def\ifsort@s#1{%
        \ifx\sort@s#1%
                \expandafter\@firstoftwo
        \else
                \expandafter\@secondoftwo
        \fi
}

% #1 - comparator
% #2 - tokens processed so far
% #3 - smallest token so far
% #4 - rest of the list
\def\sort@begin#1#2#3#4\sort@begin{%
        \ifsort@s{#4}
        {%
                \sortend{#3}%
                \sort#1{#2}%
        }% else
        {%
                \sort@go#1{#2}{#3}#4\sort@go
        }%
}

% #1 - comparator
% #2 - tokens processed so far
% #3 - smallest token so far
% #4 - token under consideration
% #5 - rest of the list
\def\sort@go#1#2#3#4#5\sort@go{%
        #1{#3}{#4}{\sort@output#1{#2}{#5}}%
}
% #1 - comparator
% #2 - tokens processed so far
% #3 - rest of the list
% #4 - smaller of the two tokens
% #5 - larger of the two tokens
\def\sort@output#1#2#3#4#5{%
        \ifsort@s{#3}
        {%
                \sortoutput{#4}%
                \sort#1{#2{#5}}%
        }% else
        {%
                \sort@begin#1{#2{#5}}{#4}#3\sort@begin
        }%
}

\def\sort@numlt#1#2#3{%
        \ifnumcomp{#1}<{#2}
        {#3{#1}{#2}}% else
        {#3{#2}{#1}}%
}

\def\sort@numgt#1#2#3{%
        \ifnumcomp{#1}>{#2}
        {#3{#1}{#2}}% else
        {#3{#2}{#1}}%
}

\def\sort@alpha#1#2#3{%
        \ifnumcomp{\pdfstrcmp{#1}{#2}}<{0}
        {#3{#1}{#2}}% else
        {#3{#2}{#1}}%
}

\newcommand*\sortnumlt{\sort\sort@numlt}
\newcommand*\sortnumgt{\sort\sort@numgt}
\newcommand*\sortalpha{\sort\sort@alpha}
\makeatother

% Change these to change out the sort outputs.
\newcommand*\sortoutput[1]{#1, }
\newcommand*\sortend[1]{#1.}
\begin{document}
\sortnumgt{87632147{55}9{8/2}}

\sortalpha{{Goodbye}{Cruel}{World}}

\renewcommand*\sortoutput[1]{#1}
\renewcommand*\sortend[1]{#1}
\edef\temp{\sortnumlt{87632147{55}9}}
\texttt{\meaning\temp}
\end{document}

I hope the code is readable. I tried to document the arguments to each function. In particular, the first argument to \sort is a comparator control sequence that must take three arguments. The first two are the two elements of the following list to compare and the third is the continuation. Basically, the comparator should expand to either #3{#1}{#2} or #3{#2}{#1} depending on #1 being "less than" #2.

I've implemented three such comparators. The first two compare lists of numbers whereas the third does alphanumeric string comparison using \pdfstrcmp. Since the number comparisons use \ifnumcomp from etoolbox, you can use arbitrary arithmetic expressions for the elements, hence {8/2} in the list.

Finally, to show that this is expandable (at least it is whenever the comparator, \sortoutput, and \sortend are), \temp is defined using \edef and its meaning is typeset to ensure that it has been set to the appropriate value: macro:->12346778955.

Note that it would also be straight-forward to thread \sortoutput and \sortend through all of these macros so that multiple \sorts could be used in the same expansion. I just didn't think about adding those until I had written all of the rest of the code (more or less).

Note further that this is selection sort and thus would take Θ(n²) time, even in the best case. However, this being TeX and it having to construct the token lists for each argument each time, I think this implementation is actually Θ(n³) time. So don't try it on large lists.

Answer 2

The following certainly works for one list, but I am not certain as to how to extend it to more than one sorted list.

\documentclass[a4paper,12pt]{report}
\usepackage{datatool}
\usepackage[top=2cm, bottom=2cm, left=1cm, right=1cm]{geometry}
\usepackage[spanish]{babel}
\usepackage{amsfonts,amssymb,amsmath}

\newcommand{\sortitem}[2]{%
  \DTLnewrow{list}%
  \DTLnewdbentry{list}{label}{#1}%
  \DTLnewdbentry{list}{description}{#2}%
}

\newenvironment{sortedlist}{%
  \DTLifdbexists{list}{\DTLcleardb{list}}{\DTLnewdb{list}}%
}{%
  \DTLsort{label}{list}%
  \begin{description}%
    \DTLforeach*{list}{\theLabel=label,\theDesc=description}{%
      \item[\theLabel] \theDesc }%
  \end{description}%
}

\begin{document}
\begin{sortedlist}
\sortitem{Leonard Euler}{Mathematician}
\sortitem{Carl Friedrich Gauss}{Mathematician}
\sortitem{August Ferdinand M"\obius}{Mathematician}
\end{sortedlist}
\end{document}

Answer 3

If you are willing to use LuaLaTeX, then you it should be possible to port the various language specific sorting functions from ConTeXt MkIV. For example see

• sort-lan.lua
• sort-ini.lua

Answer 4

A long time ago, I wrote a sorting package for LaTeX, for personal use. I have no idea how to use it or whether it works, but here is the source code:

http://www.eecs.harvard.edu/~cduan/download/?file=sortlist.sty

It requires a helper file, located at http://www.eecs.harvard.edu/~cduan/download/?file=strings.sty

Answer 5

I started using TH's code, and found that it had to be tweaked a bit for my use case. Specifically, I wanted to be able to sort things with \par in them, and wanted the sort order to be based on the value of a \ref. After struggling for a bit, I got something working, and figured it would be worth sharing my efforts here. An example document that uses it looks like this:

\documentclass{article}
\usepackage{sort}
\begin{document}
\newcounter{foo}
\refstepcounter{foo}\label{a}
\refstepcounter{foo}\label{b}

\begin{trivlist}
    \sortref{%
        {{a}{Text with some proofs about part a

        in multiple paragraphs!}}%
        {{b}{Proofs about

        the other part}}%
    }
\end{trivlist}
\end{document}

The two proofs will reorder automatically based on the order the \labels come in. The primary differences are to add \long a few places, use \newcommand instead of \newcommand*, and add a new \sortoutput that uses \getrefnumber (being careful to trim \par from its argument). The complete contents of sort.sty after these changes is:

\usepackage{etoolbox}
\usepackage{refcount}
\makeatletter
% #1 - comparator
% #2 - token list to sort
\newcommand\sort[2]{%
        \ifstrempty{#2}
        {}% else
        {%
                \sort@begin#1{}#2\sort@s\sort@begin
        }%
}

% helpers
\def\sort@s{\sort@s}
\long\def\ifsort@s#1{%
        \ifx\sort@s#1%
                \expandafter\@firstoftwo
        \else
                \expandafter\@secondoftwo
        \fi
}

% #1 - comparator
% #2 - tokens processed so far
% #3 - smallest token so far
% #4 - rest of the list
\long\def\sort@begin#1#2#3#4\sort@begin{%
        \ifsort@s{#4}
        {%
                \sortend{#3}%
                \sort#1{#2}%
        }% else
        {%
                \sort@go#1{#2}{#3}#4\sort@go
        }%
}

% #1 - comparator
% #2 - tokens processed so far
% #3 - smallest token so far
% #4 - token under consideration
% #5 - rest of the list
\long\def\sort@go#1#2#3#4#5\sort@go{%
        #1{#3}{#4}{\sort@output#1{#2}{#5}}%
}
% #1 - comparator
% #2 - tokens processed so far
% #3 - rest of the list
% #4 - smaller of the two tokens
% #5 - larger of the two tokens
\long\def\sort@output#1#2#3#4#5{%
        \ifsort@s{#3}
        {%
                \sortoutput{#4}%
                \sort#1{#2{#5}}%
        }% else
        {%
                \sort@begin#1{#2{#5}}{#4}#3\sort@begin
        }%
}

\def\sort@numlt#1#2#3{%
        \ifnumcomp{#1}<{#2}
        {#3{#1}{#2}}% else
        {#3{#2}{#1}}%
}

\def\sort@numgt#1#2#3{%
        \ifnumcomp{#1}>{#2}
        {#3{#1}{#2}}% else
        {#3{#2}{#1}}%
}

\def\sort@alpha#1#2#3{%
        \ifnumcomp{\pdfstrcmp{#1}{#2}}<{0}
        {#3{#1}{#2}}% else
        {#3{#2}{#1}}%
}

\long\def\fst#1#2{#1}
\long\def\snd#1#2{#2}
\long\def\sort@ref#1#2#3{%
    % Since #1 and #2 frequently contain newlines in their \snd part, and
    % \getrefnumber is not \long, we must take care to remove any newlines
    % *before* supplying an argument to \getrefnumber
    \edef\@leftref{\fst#1}%
    \edef\@rightref{\fst#2}%
    \ifnumcomp{\getrefnumber\@leftref}<{\getrefnumber\@rightref}%
    {#3{#1}{#2}}%
    {#3{#2}{#1}}%
}

\newcommand*\sortnumlt{\sort\sort@numlt}
\newcommand*\sortnumgt{\sort\sort@numgt}
\newcommand*\sortalpha{\sort\sort@alpha}
\newcommand\sortref{\sort\sort@ref}

% Change these to change out the sort outputs.
\newcommand\sortoutput[1]{%
    % As in the definition of \sort@ref, we must take care to remove
    % newlines before handing off to \ref
    \edef\@refname{\fst#1}%
    \item {\bf Case \ref\@refname:} \snd#1%
}
\newcommand\sortend\sortoutput

\makeatother

Answer 6

With the package dbshow (current version: v1.2). The code below sorts the list in ascending order, descending order, and multi-level order. The last example shows the independent environment.

\documentclass{article}
\usepackage{dbshow}

\newlength{\boldAcrwidth}
\setlength{\boldAcrwidth}{2cm}

\ExplSyntaxOn
\NewDocumentCommand{\boldAcrExp}{m >{\SplitList{~}}m}{%
  \makebox[\boldAcrwidth][l]{\bfseries\textit{\MakeUppercase{#1}}}%
  \ProcessList{#2}{\boldAcrFirst}%
  \unskip
}
\NewDocumentCommand{\boldAcr}{m m}{
  \exp_args:Nxx \boldAcrExp { #1 } { #2 } % need expand first
}
\ExplSyntaxOff

\NewDocumentCommand{\boldAcrFirst}{m}{%
  \boldAcrFirstAux#1 % we want a space
}
\NewDocumentCommand{\boldAcrFirstAux}{m}{%
  \textbf{\MakeUppercase{#1}}%
}

\dbNewDatabase{acronym}{acronym=str, describe=str}
\dbNewStyle{sort-list}{acronym}{
  before-code = {\begin{flushleft}},
  after-code = {\end{flushleft}},
  item-code = {\boldAcr{\dbuse{acronym}}{\dbuse{describe}} \\},
  sort = acronym,
}
\dbNewStyle[sort-list]{sort-list-desc}{acronym}{sort=acronym*}
\dbNewStyle[sort-list]{multi-sort-list}{acronym}{sort={acronym, describe}}

\newcommand\saveAcr[2]{%
  \begin{dbitem}{acronym}[acronym=#1, describe=#2]%
  \end{dbitem}%
}

\NewDocumentEnvironment { acronym } { m }
  { \dbclear{acronym} } { \dbshow{#1}{acronym} }


\begin{document}

\saveAcr{owasp}{open web application security project}
\saveAcr{dbms}{duxbury bay maritime school}
\saveAcr{dbms}{database management system}
\saveAcr{sqlia}{structured query language injection attack}

\section{Ascending Order}
\dbshow{sort-list}{acronym}
\section{Descending Order}
\dbshow{sort-list-desc}{acronym}
\section{Multi-level Sorting}
\dbshow{multi-sort-list}{acronym}

\section{More list}
% clear the database acronym and use style sort-list to display
% previous records are lost
\begin{acronym}{sort-list}
  \saveAcr{aef}{american expeditionary force}
  \saveAcr{abc}{australian broadcasting corporation}
\end{acronym}

\end{document}