# How to perform lexicographic sort on list of coordinates in LaTeX?

I need to sort a list of TikZ coordinates, first by increasing X coordinate and then by increasing Y coordinate. At the moment I do this by invoking an external Python shell, but it would be nicer to be able to do it entirely in LaTeX.

Below is a minimal working example to illustrate:

\documentclass{article}

\def\coordList{(5,5) (0,0) (2,5) (2,4) (-1, 3)}
\def\sortList#1{
% TODO: ?
}

\begin{document}
Input: \coordList

After sorting: \sortList{\coordList}

Expected result: (-1, 3) (0,0) (2,4) (2,5) (5,5)
\end{document}


The format of the list does not necessarily need to be as in the MWE; the only requirement is that they should be sorted in the end.

Update adds variant handling dimensional coordinates.

This is the adaptation of "code 4" from https://tex.stackexchange.com/a/273084/4686

I initially was going to to the Merge Sort ("code 6" from the link above), but ( is handled especially by \pdfescapestring, and spaces too, and thus opted for "code 4". This is expandable code. Should work even when parsed by TikZ. Caveat: I noticed one day that TikZ's coordinates puts a cap at about 100 expansion steps, which is very low for any serious expandable macro. It is possible to use tricks. Package xintexpr has a macro \xintthecoords which transforms a comma separated list of an even number of values into pairs of coordinates for TikZ's coordinates. Perhaps I should have written the code here to work all the way with comma separated values. Which would be convenient to feed it to \xintthecoords at the last minute to produce back the pairs of coordinates in a way tricking TikZ's expansion counter. I think about it too late, will edit if requested.

\documentclass{article}

\makeatletter
% This is based ond the "code 4" of
% https://tex.stackexchange.com/a/273084/4686,
%
% modified to handle pairs (a, b) (c,d)(e, f) (g,h) etc...
%
% acts expandably. Lexicographic order.

\makeatletter

% Here we define the comparison macro for pairs (a,b)
% We assume decimal numbers acceptable to \ifdim tests

\long\def\xintdothis #1#2\xintorthat #3{\fi #1}%
\let\xintorthat \@firstofone

\long\def\@thirdoffour  #1#2#3#4{#3}%
\long\def\@fourthoffour #1#2#3#4{#4}%

\def\IfFirstPairIsGreaterTF #1#2{\@IfFirstPairIsGreaterTF #1,#2,}%

\def\@IfFirstPairIsGreaterTF #1,#2,#3,#4,{%
\ifdim #1\p@=#3\p@
\xintdothis{%
\ifdim #2\p@>#4\p@\expandafter\@firstoftwo
\else\expandafter\@secondoftwo\fi}\fi
\ifdim #1\p@>#3\p@\expandafter\@thirdoffour
\else\expandafter\@fourthoffour\fi
\xintorthat{}%
}%

% not needed for numerical inputs
% \catcode! 3
% \catcode? 3

% Here there is a very strange \romannumeral0\romannumeral0, this is
% due to some convoluted scheme to avoid double spaces or no spaces
% in between coordinate pairs. Trust me.
\def\QSpairs {\romannumeral0\romannumeral0\qspairs }%
% first we check if empty list
\def\qspairs   #1{\expandafter\qspairs@a\romannumeral-0#1(!)(?)}%
\def\qspairs@a #1(#2{\ifx!#2\expandafter\qspairs@abort\else
\expandafter\qspairs@b\fi (#2}%
\edef\qspairs@abort #1(?){\space\space}%
%
% we check if empty of single and if not pick up the first as Pivot:
\def\qspairs@b #1(#2)#3(#4){\ifx?#4\xintdothis\qspairs@empty\fi
\ifx!#4\xintdothis\qspairs@single\fi
\xintorthat \qspairs@separate {}{}{#2}(#4)}%
\def\qspairs@empty  #1(?){ }%
\edef\qspairs@single #1#2#3#4(?){\space\space(#3)}%
\def\qspairs@separate #1#2#3#4(#5)%
{%
\ifx!#5\expandafter\qspairs@separate@done\fi
\IfFirstPairIsGreaterTF {#5}{#3}%
\qspairs@separate@appendtogreater
\qspairs@separate@appendtosmaller {#5}{#1}{#2}{#3}%
}%
%
\def\qspairs@separate@appendtogreater #1#2{\qspairs@separate {#2 (#1)}}%
\def\qspairs@separate@appendtosmaller #1#2#3{\qspairs@separate {#2}{#3 (#1)}}%
%
\def\qspairs@separate@done\IfFirstPairIsGreaterTF #1#2%
\qspairs@separate@appendtogreater
\qspairs@separate@appendtosmaller #3#4#5#6(?)%
{%
\expandafter\qspairs@f\expandafter
{\romannumeral0\qspairs@b #4(!)(?)}{\qspairs@b #5(!)(?)}{ (#2)}%
}%
%
\def\qspairs@f #1#2#3{#2#3#1}%
%
% \catcode! 12
% \catcode? 12

\makeatother

\usepackage{geometry}

\begin{document}
\Large

\def\coordList{(5,5) (0,0) (2,5) (2,4) (-1, 3)}

Input: \coordList

After sorting: \QSpairs{\coordList}

Expected result: (-1, 3) (0,0) (2,4) (2,5) (5,5)

\bigskip

\def\coordList {
(735.578, -0.5)
(408.866, 7.2)
(513.653, 1)
(465.136, 17)
(323.362, 17)
(408.866, 3)
(408.866, 4)
(735.578, -0.1)
(408.866, 7.1)
(408.866, 5)
(886.204, 1.4)
(408.866, 2)
(649.711, 17)
(735.578, -1)
(886.204, 1.3)
(886.204, 1.2)
(254.715, 17)
(408.866, 6)
(886.204, 1)
(504.730, 17)
(504.730, -100)
(186.578, -2)
(735.578, -0.4)
(608.552, 0)
(408.866, 7.21)
(412.004, -1)
(886.204, 1.1)
(195.793, 17)
(408.866, 1)
(388.683, 17)
(140.974, -10)
(408.866, 7.201)
}

Input: \coordList

Output: \QSpairs{\coordList}

\end{document}


----

Update handling dimensional coordinates.

\documentclass{article}
\makeatletter
% This is based ond the "code 4" of
% https://tex.stackexchange.com/a/273084/4686,
%
% modified to handle pairs (a, b) (c,d)(e, f) (g,h) etc...
%
% acts expandably. Lexicographic order.

\makeatletter

% This variant assumes that all a's and b's are explicit dimension coordinates
% like 5pt or 20ex

\long\def\xintdothis #1#2\xintorthat #3{\fi #1}%
\let\xintorthat \@firstofone

\long\def\@thirdoffour  #1#2#3#4{#3}%
\long\def\@fourthoffour #1#2#3#4{#4}%

\def\IfFirstPairIsGreaterTF #1#2{\@IfFirstPairIsGreaterTF #1,#2,}%

% Th code handles also \dimen's like \ht\box0
% (but the output then can not be directly printed, it can
% only be used in contexts accepting \dimen's)
% Variant handling also things like \ht\box0
\def\@IfFirstPairIsGreaterTF #1,#2,#3,#4,{%
\ifdim \dimexpr(#1)-(#3)=\z@
\xintdothis{%
\ifdim \dimexpr (#2)-(#4)>\z@\expandafter\@firstoftwo
\else\expandafter\@secondoftwo\fi}\fi
\ifdim \dimexpr(#1)-(#3)>\z@\expandafter\@thirdoffour
\else\expandafter\@fourthoffour\fi
\xintorthat{}%
}%

% not needed for numerical inputs
% \catcode! 3
% \catcode? 3
% Here there is a very strange \romannumeral0\romannumeral0, this is
% due to some convoluted scheme to avoid double spaces or no spaces
% in between coordinate pairs. Trust me.
\def\QSpairs {\romannumeral0\romannumeral0\qspairs }%
% first we check if empty list (else \qsfull@finish will not find a comma)
\def\qspairs   #1{\expandafter\qspairs@a\romannumeral-0#1(!)(?)}%
\def\qspairs@a #1(#2{\ifx!#2\expandafter\qspairs@abort\else
\expandafter\qspairs@b\fi (#2}%
\edef\qspairs@abort #1(?){\space\space}%
%
% we check if empty of single and if not pick up the first as Pivot:
\def\qspairs@b #1(#2)#3(#4){\ifx?#4\xintdothis\qspairs@empty\fi
\ifx!#4\xintdothis\qspairs@single\fi
\xintorthat \qspairs@separate {}{}{#2}(#4)}%
\def\qspairs@empty  #1(?){ }%
\edef\qspairs@single #1#2#3#4(?){\space\space(#3)}%
\def\qspairs@separate #1#2#3#4(#5)%
{%
\ifx!#5\expandafter\qspairs@separate@done\fi
\IfFirstPairIsGreaterTF {#5}{#3}%
\qspairs@separate@appendtogreater
\qspairs@separate@appendtosmaller {#5}{#1}{#2}{#3}%
}%
%
\def\qspairs@separate@appendtogreater #1#2{\qspairs@separate {#2 (#1)}}%
\def\qspairs@separate@appendtosmaller #1#2#3{\qspairs@separate {#2}{#3 (#1)}}%
%
\def\qspairs@separate@done\IfFirstPairIsGreaterTF #1#2%
\qspairs@separate@appendtogreater
\qspairs@separate@appendtosmaller #3#4#5#6(?)%
{%
\expandafter\qspairs@f\expandafter
{\romannumeral0\qspairs@b #4(!)(?)}{\qspairs@b #5(!)(?)}{ (#2)}%
}%
%
\def\qspairs@f #1#2#3{#2#3#1}%
%
% \catcode! 12
% \catcode? 12

\makeatother

\usepackage{geometry}

\begin{document}
\Large

\def\coordList{(5pt, 5pt) (0pt, 0pt) (2pt, 5pt) (2pt, 5bp) (2pt, 4pt) (2bp, 4pt) (-1pt, 3pt)}

Input: \coordList

After sorting: \QSpairs{\coordList}

\end{document}


• Too late now but I started from the code which is not very efficient if the input has many many many exactly identical items. The better code would separate into three: less, equal and greater than pivot. – user4686 Dec 15 '15 at 22:49
• I tried to modify the code to allow dimension coordinates (such as 5pt), but I can't seem to get it to work... =/ – gablin Dec 17 '15 at 10:48
• @gablin I will add variant to handle the case of dimension coordinates. Allowing both with and without explicit dimensional unit at the same time would require an extra step (using pt as default is absent). – user4686 Dec 17 '15 at 13:10
• Perfect! This is just exactly what I needed! – gablin Dec 17 '15 at 14:19
• glad it helped :-) – user4686 Dec 17 '15 at 14:42

Package forest implements a quicksort algorithm that you could use. It is described in section 8.2 of the manual (the implementation part).

To use the \forest@sort macro, one must define two macros:

1. A macro that sorts two items: below, \sortcoordinates.

2. A macro that copies (in the sense of TeXs \let) one item onto another: below, \letcoordinates.

As the array-sorting in forest is really a package-internal thing, there are no nice macros for setting and reading arrays accompanying it, but that's not a major obstacle as arrayjobx can be used. (Package multido is used to walk through the array.)

The code below uses an implementational detail of arrayjobx, namely the fact that the item 42 of array coordinates will be stored in control sequence coordinates42~.

\documentclass{article}

\usepackage{arrayjobx}
\usepackage{multido}
\usepackage{forest}

\makeatletter
\def\letcoordinates#1#2{\csletcs{coordinates#1\string~}{coordinates#2\string~}}
\def\parsecoordinate(#1,#2)#3#4{%
\def#3{#1 pt}%
\def#4{#2 pt}%
}
\def\sortcoordinates#1#2{%
\expandafter\expandafter\expandafter\parsecoordinate\csname coordinates#1\string~\endcsname\firstx\firsty
\expandafter\expandafter\expandafter\parsecoordinate\csname coordinates#2\string~\endcsname\secondx\secondy
\forest@sort@cmptwodimcs{firstx}{firsty}{secondx}{secondy}%
}
\makeatother

\begin{document}

\newarray\coordinates
\def\ncoordinates{5}
\newcounter{i}
Unsorted: \multido{\i=1+1}{\ncoordinates}{\coordinates(\i),}

\makeatletter
\forest@sort\sortcoordinates\letcoordinates\forest@sort@ascending{1}{\ncoordinates}%
\makeatother
Sorted: \multido{\i=1+1}{\ncoordinates}{\coordinates(\i),}

\end{document}


Output:

Unsorted: (5,5),(0,0),(2,5),(2,4),(-1, 3),
Sorted: (-1, 3),(0,0),(2,4),(2,5),(5,5),

• The code will actually be part of a package that I'm developing for drawing TikZ figures, so I will anyhow need to create the array incrementally. Is there a way of adding the elements, one by one, to the array? – gablin Dec 11 '15 at 14:19
• \coordinates(n)={value}. See the arrayjobx documentation for more info. – Sašo Živanović Dec 11 '15 at 14:26
• I tried that before but couldn't get it to work properly. Turned out I was using it wrongly. =) But now I got another problem: If I put in a macro into one of the element (instead of a hard-coded coordinate), I get a compilation error: ! Use of \parsecoordinate doesn't match its definition. \coordinates1~ ->\mymacro Any idea on how to work around this? – gablin Dec 15 '15 at 15:48
• Probably an issue with expansion. Maybe arrayjob's \expandarrayelementtrue could help. – Sašo Živanović Dec 16 '15 at 8:01