| 1 |
% \iffalse meta-comment |
| 2 |
% |
| 3 |
% Copyright (C) 2013 by Robert J Lee |
| 4 |
% |
| 5 |
% This file may be distributed and/or modified under the |
| 6 |
% conditions of the LaTeX Project Public License, either |
| 7 |
% version 1.2 of this license or (at your option) any later |
| 8 |
% version. The latest version of this license is in: |
| 9 |
% |
| 10 |
% http://www.latex-project.org/lppl.txt |
| 11 |
% |
| 12 |
% and version 1.2 or later is part of all distributions of |
| 13 |
% LaTeX version 1999/12/01 or later. |
| 14 |
% |
| 15 |
% \fi |
| 16 |
% |
| 17 |
% \iffalse |
| 18 |
%<package>\NeedsTeXFormat{LaTeX2e}[1999/12/01] |
| 19 |
%<package>\ProvidesPackage{arraysort} |
| 20 |
%<package> [2013/09/04 v1.0 sorting arrayjobx arrays] |
| 21 |
% |
| 22 |
%<*driver> |
| 23 |
\documentclass{ltxdoc} |
| 24 |
\usepackage[comparestr,comparenum,randompart]{arraysort} |
| 25 |
\EnableCrossrefs |
| 26 |
\usepackage{indentfirst} |
| 27 |
\usepackage{showexpl} |
| 28 |
\usepackage{multido} |
| 29 |
\newbool{excludelongtest} |
| 30 |
\setbool{excludelongtest}{true} % change to false for slow test |
| 31 |
\CodelineIndex |
| 32 |
\RecordChanges |
| 33 |
\begin{document} |
| 34 |
\DocInput{arraysort.dtx} |
| 35 |
\end{document} |
| 36 |
%</driver> |
| 37 |
% \fi |
| 38 |
% |
| 39 |
% \CharacterTable |
| 40 |
% {Upper-case \A\B\C\D\E\F\G\H\I\J\K\L\M\N\O\P\Q\R\S\T\U\V\W\X\Y\Z |
| 41 |
% Lower-case \a\b\c\d\e\f\g\h\i\j\k\l\m\n\o\p\q\r\s\t\u\v\w\x\y\z |
| 42 |
% Digits \0\1\2\3\4\5\6\7\8\9 |
| 43 |
% Exclamation \! Double quote \" Hash (number) \# |
| 44 |
% Dollar \$ Percent \% Ampersand \& |
| 45 |
% Acute accent \' Left paren \( Right paren \) |
| 46 |
% Asterisk \* Plus \+ Comma \, |
| 47 |
% Minus \- Point \. Solidus \/ |
| 48 |
% Colon \: Semicolon \; Less than \< |
| 49 |
% Equals \= Greater than \> Question mark \? |
| 50 |
% Commercial at \@ Left bracket \[ Backslash \\ |
| 51 |
% Right bracket \] Circumflex \^ Underscore \_ |
| 52 |
% Grave accent \` Left brace \{ Vertical bar \| |
| 53 |
% Right brace \} Tilde \~} |
| 54 |
% |
| 55 |
% \CheckSum{236} |
| 56 |
% |
| 57 |
% \changes{v1.0}{2013/09/04}{Initial version} |
| 58 |
% |
| 59 |
% \GetFileInfo{arraysort.sty} |
| 60 |
% |
| 61 |
% \DoNotIndex{\let, \edef, \xdef, \relax, \newcommand} |
| 62 |
% \DoNotIndex{\csname, \endcsname, \ifcsname} |
| 63 |
% \DoNotIndex{\OR, \if, \else, \fi, \equal, \ifthenelse, \iftoggle} |
| 64 |
% \DoNotIndex{\arabic, \addtocounter, \value, \setcounter, \stepcounter} |
| 65 |
% \DoNotIndex{\g@addto@macro, \string} |
| 66 |
% |
| 67 |
% |
| 68 |
%\def\IsPositive#1{% http://www.tex.ac.uk/cgi-bin/texfaq2html?label=isitanum |
| 69 |
% TT\fi |
| 70 |
% \ifcat_\ifnum0<0#1 _\else A\fi |
| 71 |
%} |
| 72 |
% |
| 73 |
% \newenvironment{exg}[1]{\pagebreak[3]\begin{center} |
| 74 |
% \line(1,0){250} |
| 75 |
% \end{center}\nopagebreak~\par\nopagebreak\textit{Example:~~\texttt{#1}}\par\vspace{-1em}}{\begin{center} |
| 76 |
% \line(1,0){250} |
| 77 |
% \end{center}\delarray{A}\noindent} |
| 78 |
% |
| 79 |
% \title{The Arraysort Package\thanks{This document corresponds to \textsf{Arraysort}~\fileversion, dated \filedate.}} |
| 80 |
% \author{Robert J Lee \\ [email protected]} |
| 81 |
% |
| 82 |
% \maketitle |
| 83 |
% |
| 84 |
% \begin{abstract} |
| 85 |
% |
| 86 |
% The |arraysort| package allows the user to sort an array (defined |
| 87 |
% with the |arrayjobx| package), or a portion of such an array, |
| 88 |
% without using external files or commands or requiring a second run |
| 89 |
% of \LaTeX. |
| 90 |
% |
| 91 |
% Basic comparators are provided for sorting by ASCII-code or for |
| 92 |
% sorting numeric values. Options to tweak performance of the sort are |
| 93 |
% also provided, should they be needed. |
| 94 |
% |
| 95 |
% \end{abstract} |
| 96 |
% |
| 97 |
% \section*{Introduction} |
| 98 |
% |
| 99 |
% This package implements an in-place Quick Sort algorithm for |
| 100 |
% \LaTeX. Quick-Sort is a recursive and highly configurable algorithm |
| 101 |
% for sorting of arrays. |
| 102 |
% |
| 103 |
% |
| 104 |
% \section{Usage} |
| 105 |
% |
| 106 |
% The |arraysort| package requires the |arrayjobx| package, which |
| 107 |
% provides several methods to define an array of values. This docment |
| 108 |
% assumes that you are familiar with |arrayjobx|. A number of examples |
| 109 |
% are provided to sort a small array named $A$; the package can sort |
| 110 |
% much larger arrays than those shown including arrays whose contents |
| 111 |
% are stored unexpanded (although they will be expanded when comparing |
| 112 |
% them using the provided comparators). |
| 113 |
% |
| 114 |
% \subsection*{Sorting by Text} |
| 115 |
% |
| 116 |
% \DescribeMacro{\sortArray} |
| 117 |
% |
| 118 |
% To sort the first |10| elemnets of $A$, you can simply write: |
| 119 |
% |\sortArray{|10|}{|$A$|}| |
| 120 |
% |
| 121 |
% |\sortArray| takes two mandatory parameters: the first is the |
| 122 |
% number of elements to sort, the second is the name of the array. |
| 123 |
% |
| 124 |
% \iffalse |
| 125 |
%<*example> |
| 126 |
% \fi |
| 127 |
\begin{exg}{$\backslash$sortArray with words}\begin{LTXexample} |
| 128 |
\newarray{A} |
| 129 |
\readarray{A}{The&Quick&Brown&% |
| 130 |
Fox&Jumps&Over&the&Lazy&Dog} |
| 131 |
\sortArray{9}{A} |
| 132 |
\A(1) \A(2) \A(3) \A(4) \A(5) |
| 133 |
\A(6) \A(7) \A(8) \A(9) |
| 134 |
\end{LTXexample}\end{exg} |
| 135 |
% \iffalse |
| 136 |
%</example> |
| 137 |
% \fi |
| 138 |
% Note that the default is to sort by character code order, so the |
| 139 |
% lower-case ``the'' is sorted after the words starting with |
| 140 |
% upper-case letters. This is a limitation of the default sorting |
| 141 |
% method, but other ways of sorting are possible. |
| 142 |
% |
| 143 |
% \subsection*{Sorting Numbers} |
| 144 |
% |
| 145 |
% The default sorting method can have surprising results when sorting |
| 146 |
% arrays of numbers: |
| 147 |
% \iffalse |
| 148 |
%<*example> |
| 149 |
% \fi |
| 150 |
\begin{exg}{$\backslash$sortArray with numbers}\begin{LTXexample} |
| 151 |
\newarray{A} |
| 152 |
\readarray{A}{78&4&85&1&28&6} |
| 153 |
\sortArray{6}{A} |
| 154 |
\A(1) \A(2) \A(3) \A(4) \A(5) \A(6) |
| 155 |
\end{LTXexample}\end{exg} |
| 156 |
% \iffalse |
| 157 |
%</example> |
| 158 |
% \fi |
| 159 |
% Here, the numbers are still sorted in dictionary order, |
| 160 |
% which was probably not the intent, as the number~28 would usually be |
| 161 |
% sorted after the number~6, even though the first digit of~28 is |
| 162 |
% smaller than the first digit of~6. |
| 163 |
% |
| 164 |
% To solve this problem, an alternative comparator can be used: |
| 165 |
% \iffalse |
| 166 |
%<*example> |
| 167 |
% \fi |
| 168 |
\begin{exg}{$\backslash$sortArray with |arraysortcomparenum|}\begin{LTXexample} |
| 169 |
\newarray{A} |
| 170 |
\readarray{A}{78&4&85&1&28&6} |
| 171 |
\sortArray[arraysortcomparenum]{6}{A} |
| 172 |
\A(1) \A(2) \A(3) \A(4) \A(5) \A(6) |
| 173 |
\end{LTXexample}\end{exg} |
| 174 |
% \iffalse |
| 175 |
%</example> |
| 176 |
% \fi |
| 177 |
% The |arraysortcomparenum| comparator is passed as the first optional |
| 178 |
% argument; this option sorts by numerical order in the intuitive |
| 179 |
% way --- but it will error if a value in the array is not a number. |
| 180 |
% |
| 181 |
% This option requires additional package options; see section below. |
| 182 |
% |
| 183 |
% \subsection*{Sorting part of an array} |
| 184 |
% |
| 185 |
% A second optional argument is accepted for the start of the range to |
| 186 |
% be sorted. So you can easily sort only a segment of an array: |
| 187 |
% \iffalse |
| 188 |
%<*example> |
| 189 |
% \fi |
| 190 |
\begin{exg}{$\backslash$sortArray with range}\begin{LTXexample} |
| 191 |
\newarray{A} |
| 192 |
\readarray{A}{P&Y&F&G&% |
| 193 |
A&O&E&U&I&D&H&T&N&S&% |
| 194 |
Q&J&K&X&B&M&W&V&Z} |
| 195 |
\sortArray[arraysortcomparestr][8]{21}{A} |
| 196 |
\A(1)\A(2)\A(3)\A(4)\A(5)\A(6)\A(7)% |
| 197 |
\textit{\A(8)\A(9)\A(10)\A(11)\A(12)% |
| 198 |
\A(13)\A(14)\A(15)\A(16)}\A(17)\A(18)% |
| 199 |
\A(19)\A(20)\A(21)\A(22)\A(23) |
| 200 |
\end{LTXexample}\end{exg} |
| 201 |
% \iffalse |
| 202 |
%</example> |
| 203 |
% \fi |
| 204 |
% The start of the range must be the second optional parameter, so you |
| 205 |
% need to specify the comparator as well. The default comparator is |
| 206 |
% |arraysortcomparestr| as shown here. |
| 207 |
% |
| 208 |
% The example shows sorting the italicised region of 8--21 letters, |
| 209 |
% originally arranged in the relatively jumbled order of the Dvorak |
| 210 |
% keyboard. |
| 211 |
% |
| 212 |
% \subsection*{Sorting by Custom Order} |
| 213 |
% |
| 214 |
% While it is useful to sort an array into numbers or alphabetically, |
| 215 |
% it is possible to sort an array into any order. To do this, you need |
| 216 |
% to write a \textit{comparator}; this is a macro that is passed 2 |
| 217 |
% values from the array and evaluates which should appear first. |
| 218 |
% |
| 219 |
% A custom comparotor macro can be passed by appending its name as the |
| 220 |
% optional argument is passed at the end of the |\sortarray| macro |
| 221 |
% call. |
| 222 |
% |
| 223 |
% Your comparator macro must set the value of two toggles: |
| 224 |
% |
| 225 |
% \DescribeMacro{arraysortresult} |
| 226 |
% Set |arraysortresult| to true if the first parameter is less than |
| 227 |
% the second (\textit{ie} if the parameters are presented in sorted |
| 228 |
% order). |
| 229 |
% |
| 230 |
% \DescribeMacro{arraysortresequal} |
| 231 |
% |arraysortresequal| should be set by a comparator if both values are |
| 232 |
% equal. It is not necessary to set |arraysortresult| if |
| 233 |
% |arraysortresequal| is set to true. |
| 234 |
% |
| 235 |
% Both toggles can be set using the macros |\toggletrue{|\textit{togglename}|}| |
| 236 |
% and |\togglefalse{|\textit{togglename}|}| defined in the |etoolbox| |
| 237 |
% package, where \textit{togglename} is the name of the toggle to be |
| 238 |
% set or cleared. |
| 239 |
% |
| 240 |
% The name of the comparator is passed to the sort algorithm as the |
| 241 |
% first optional parameter; the leading $\backslash$ should be |
| 242 |
% omitted. |
| 243 |
% |
| 244 |
% \iffalse |
| 245 |
%<*example> |
| 246 |
% \fi |
| 247 |
\begin{exg}{$\backslash$sortArray with custom comparator}\begin{LTXexample} |
| 248 |
\newcommand{\cmpnumbersfirst}[2]{% |
| 249 |
\edef\cmpA{#1}% |
| 250 |
\edef\cmpB{#2}% |
| 251 |
\if\IsPositive{\cmpA}% |
| 252 |
\if\IsPositive{\cmpB}% |
| 253 |
\arraysortcomparenum{\cmpA}{\cmpB}% |
| 254 |
\else% |
| 255 |
\togglefalse{arraysortresequal}% |
| 256 |
\toggletrue{arraysortresult}% |
| 257 |
\fi% |
| 258 |
\else% |
| 259 |
\if\IsPositive{\cmpB}% |
| 260 |
\togglefalse{arraysortresequal}% |
| 261 |
\togglefalse{arraysortresult}% |
| 262 |
\else% |
| 263 |
\arraysortcomparestr{\cmpA}{\cmpB}% |
| 264 |
\fi% |
| 265 |
\fi% |
| 266 |
} |
| 267 |
\newarray{A} |
| 268 |
\readarray{A}{apple&2&rabbits&12&-4} |
| 269 |
\sortArray[cmpnumbersfirst]{5}{A} |
| 270 |
\A(1) \A(2) \A(3) \A(4) \A(5) |
| 271 |
\end{LTXexample}\end{exg} |
| 272 |
% \iffalse |
| 273 |
%</example> |
| 274 |
% \fi |
| 275 |
% This example uses the following definition of |\IsPositive| from |
| 276 |
% the |cite| package\footnote{See |
| 277 |
% \texttt{http://www.tex.ac.uk/cgi-bin/texfaq2html?label=isitanum}} |
| 278 |
% |
| 279 |
% \begin{verbatim} |
| 280 |
% \def\IsPositive#1{% |
| 281 |
% TT\fi |
| 282 |
% \ifcat_\ifnum0<0#1 _\else A\fi |
| 283 |
% } |
| 284 |
% \end{verbatim} |
| 285 |
% |
| 286 |
% This custom sort places positive integers first, in numerical order, |
| 287 |
% then everything else in default order. |
| 288 |
% |
| 289 |
% The |\cmpnumbersfirst| macro tests each parameter to see if is a |
| 290 |
% positive number. If both parameters are positive integers, then it delegates |
| 291 |
% to the |arraysortcomparenum| macro so that integers are sorted in |
| 292 |
% sequence. If both parameters are not positive integers then the |
| 293 |
% default sort is used. Otherwise, |arraysortresult| is set to true if |
| 294 |
% |#1| is a positive integer and |#2| is not, or false if it is the |
| 295 |
% other way around; this guarantees that positive numbers are sorted first. |
| 296 |
% |
| 297 |
% \textsc{tip:} Most comparators will fully expand their arguments |
| 298 |
% only once per comparison, to ensure that the sorting order remains |
| 299 |
% appropriate. That is the reason for the |\edef| in the above |
| 300 |
% example, which expands and copies the parameter into a temporary |
| 301 |
% macro. This is useless when passing individual string arguments, as |
| 302 |
% in this example, but prevents unstable behaviour when arguments |
| 303 |
% could change when reevaluated, such as when a macro contains the |
| 304 |
% current time or a pseudorandom value. |
| 305 |
% |
| 306 |
% \subsection*{Changing the Partitioning Scheme} |
| 307 |
% |
| 308 |
% The partitioning scheme does not affect the final sorting order |
| 309 |
% (unless you write your own that does not use the comparator argument) |
| 310 |
% but may affect how long it takes \LaTeX\ to sort your array. In |
| 311 |
% general it is recommended to use the default scheme, unless you are |
| 312 |
% sorting a very large array and find the |
| 313 |
% performance is unacceptable. |
| 314 |
% |
| 315 |
% To change the partitioning scheme, an optional argument can be added |
| 316 |
% to the end of the |\sortArray| macro, thus: |
| 317 |
% \iffalse |
| 318 |
%<*example> |
| 319 |
% \fi |
| 320 |
\begin{exg}{$\backslash$sortArray with custom |
| 321 |
partition}\begin{LTXexample} |
| 322 |
\newarray{A} |
| 323 |
\readarray{A}{e&d&c&b&a} |
| 324 |
\sortArray{5}{A}% |
| 325 |
[sortArrayPartitionRand] |
| 326 |
\A(1) \A(2) \A(3) \A(4) \A(5) |
| 327 |
\end{LTXexample}\end{exg} |
| 328 |
% \iffalse |
| 329 |
%</example> |
| 330 |
% \fi |
| 331 |
% Here, the writer of the package knows that $A$ is not randomised |
| 332 |
% before it is sorted, so uses the |sortArrayPartitionRand| to |
| 333 |
% partition the array at random. This avoids the worst-case |
| 334 |
% performance of the sorting algorithm. |
| 335 |
% |
| 336 |
% The performance of each partitioning method is discussed in detail |
| 337 |
% where it is defined; you should also read the section on the |
| 338 |
% in-place quick-sort algorithm to understand the purpose of each |
| 339 |
% algorithm. |
| 340 |
% |
| 341 |
% The partition name is just the name of a macro, so you can easily |
| 342 |
% write your own. It must take four parameters: |
| 343 |
% \begin{enumerate} |
| 344 |
% \item The name of a comparator macro, described above |
| 345 |
% \item The start index (inclusive) of the array segment to be partitioned |
| 346 |
% \item The end index (inclusive) of the array segment to be |
| 347 |
% partitioned |
| 348 |
% \item The name of the array to be partitioned |
| 349 |
% \end{enumerate} |
| 350 |
% |
| 351 |
% The macro should generate no output as it may be called multiple |
| 352 |
% times with different array segments to partition. It should set |
| 353 |
% |arraysort@partpos| to the current value of the partition element. |
| 354 |
% |
| 355 |
% Values that are equal to the partition value may be sorted into |
| 356 |
% either segment. A sorting algorithm that retains the relative order |
| 357 |
% of equal values is known as a \textit{stable sorting algorithm}; if |
| 358 |
% this is required, then the partitioning algorithm must |
| 359 |
% retain the relative position of each element in each sub-array, |
| 360 |
% not just those which are equal to the pivot. \textbf{The supplied |
| 361 |
% partitioning algorithms make no claim to be a stable sort}, |
| 362 |
% and stable sort semantics of the partitioning algorithm should |
| 363 |
% \textbf{not be relied on for future versions}. |
| 364 |
% |
| 365 |
% In general, it is sufficient to identify the partition element |
| 366 |
% within the array and swap it with the first element, then use |
| 367 |
% |\sortArrayPartitionFirst| |
| 368 |
% |
| 369 |
% \textsc{Note}: It is important to ensure that all elements are |
| 370 |
% expanded only once during the partition, as it is theoretically |
| 371 |
% possible for a macro to expand to different values each time it is |
| 372 |
% expanded. |
| 373 |
% |
| 374 |
% \subsection*{All Package Options} |
| 375 |
% |
| 376 |
% Package options are passed on the |\usepackage| line near the top of |
| 377 |
% your document. A comma-separated list may be supplied, like this: |
| 378 |
% |
| 379 |
% \verb!\usepackage[comparestr,comparenum,randompart]{arraysort}! |
| 380 |
% |
| 381 |
% \DescribeMacro{comparestr} |
| 382 |
% The |comparestr| option requires the |pdftexcmds| package to be |
| 383 |
% installed and to run |pdflatex|. It is currently the default sort |
| 384 |
% option, so you must either supply the |comparestr| option or specify |
| 385 |
% a comparator explicitly. |
| 386 |
% |
| 387 |
% \DescribeMacro{comparenum} |
| 388 |
% The |comparenum| option defines the |arraysortcomparenum| |
| 389 |
% comparator, which allows you to sort arrays comparing numbers by |
| 390 |
% numeric value instead of by name. |
| 391 |
% |
| 392 |
% \DescribeMacro{randompart} |
| 393 |
% The |randompart| macro requires the |lcg| package to be |
| 394 |
% installed. It defines the |sortArrayPartitionRand| option to |
| 395 |
% partition arrays using a pseudorandom sequence. |
| 396 |
% This option repeatedly calls |\reinitrand|, which resets the value |
| 397 |
% of the pseudorandom sequence as well as the maximum and minimum |
| 398 |
% values generated, so you should take care if using the |lcg| package |
| 399 |
% outwith this package. At minimum, you should call |\reinitrand| |
| 400 |
% yourself after every sort, and possibly within macros if |\rand| is |
| 401 |
% used. Be aware that this will output whitespace unless care is taken |
| 402 |
% to consume it before it is output. |lcg| will output warnings about |
| 403 |
% reusing an existing counter; these can be safely ignored as |
| 404 |
% |sortArrayPartitionRand| intentionally reuses the counter to prevent |
| 405 |
% exhaustion of counters with large sorts. |
| 406 |
% |
| 407 |
% \pagebreak |
| 408 |
% \section{Method: The In-Place Quick-Sort Algorithm} |
| 409 |
% |
| 410 |
% Quick-sort is a practical example of a recursive algorithm. |
| 411 |
% |
| 412 |
% \subsubsection*{Definition of terms:} |
| 413 |
% |
| 414 |
% \begin{description} |
| 415 |
% \item[Partition] A single element from the array. |
| 416 |
% \item[Segment] A contiguous group of elements from the array. |
| 417 |
% \end{description} |
| 418 |
% |
| 419 |
% The general approach is to divide the array into two smaller arrays, |
| 420 |
% then sort each smaller array in turn. |
| 421 |
% |
| 422 |
% The inital array segment is the entire array. |
| 423 |
% |
| 424 |
% The basic steps are: |
| 425 |
% |
| 426 |
% \begin{enumerate} |
| 427 |
% \item Determine $A_P$, the index of the partition element within the |
| 428 |
% current array segment. In practice, this must be done in constant |
| 429 |
% time~[$O(1)$] or the sort becomes slow. |
| 430 |
% \item Partition the array into two array segments, separated by a |
| 431 |
% partition, in linear time~[$O(N)$]. |
| 432 |
% \item Quick-sort the first array segment |
| 433 |
% \item Quick-sort the second array segment |
| 434 |
% \end{enumerate} |
| 435 |
% |
| 436 |
% The first step is choosing the partition element, $A_P$. This may be |
| 437 |
% any element from the array segment, although the fastest results are |
| 438 |
% achieved by selecting the median value. Many algorithms exist to |
| 439 |
% perform this ``best guess''. |
| 440 |
% |
| 441 |
% The next step is partitioning. Other than the partition element, |
| 442 |
% every element in the array is iterated over in turn. Any value less |
| 443 |
% than the partition value~$P$ is moved to the left of the partition |
| 444 |
% (lower index than $A_P$), and any value greater than the partition |
| 445 |
% is moved to its right (higher index than $A_P$). |
| 446 |
% |
| 447 |
% So, if there are $N$ elements in an array~$A$, the original array is |
| 448 |
% given by: |
| 449 |
% \begin{eqnarray*} |
| 450 |
% & A_0 \dots A_n & |
| 451 |
% \end{eqnarray*} |
| 452 |
% |
| 453 |
% After the partitioning stage, the partitioned array is given by: |
| 454 |
% \begin{eqnarray*} |
| 455 |
% & A_0 \dots A_{(P-1)} , A_P , A_{(P+1)} \dots A_N & |
| 456 |
% \end{eqnarray*} |
| 457 |
% where $A_P$ is the partition and $P$ is the index of the |
| 458 |
% partition. |
| 459 |
% |
| 460 |
% $A_0 \dots A_{(P-1)}$ defines the first array segment to be |
| 461 |
% sorted and $A_{(P+1)} \dots A_N$ defines the second. |
| 462 |
% |
| 463 |
% Each array segment is considered to be sorted if it contains one |
| 464 |
% element or less; otherwise, each are presented to the entire |
| 465 |
% quick-sort algorithm to be sorted. |
| 466 |
% |
| 467 |
% Each iteration through the algorithm divides the array into smaller |
| 468 |
% segments, each of which is always sorted relative to the other |
| 469 |
% segments. Once the segment size is as small as one element, the |
| 470 |
% entire array is sorted. |
| 471 |
% |
| 472 |
% \section{Possible Future Improvements} |
| 473 |
% |
| 474 |
% \begin{itemize} |
| 475 |
% \item It should be possible to sort macro contents by their |
| 476 |
% unexpanded values |
| 477 |
% \item It may also be possible to sort macro contents in a |
| 478 |
% case-insensitive manner (depending on language). Note that sorting |
| 479 |
% mixed-language, mixed-alphabet content in a standard-complient |
| 480 |
% manner is not always possible. |
| 481 |
% \item Further speed improvemnts are possible; in particular, it is |
| 482 |
% often faster to defer to a lower-overhead $O(n^2)$ sorting algorithm |
| 483 |
% when the number of array segment elements is smaller than some threshold |
| 484 |
% value (quick-sort is inefficient at sorting small arrays, but |
| 485 |
% often produces many of them to be sorted). |
| 486 |
% \item More sorting and partitining options. I am undecided about |
| 487 |
% passing options \textit{versus}\ simply defining multiple macros; |
| 488 |
% certainly the chance of a name collision is very small with the |
| 489 |
% naming convention used so far. |
| 490 |
% \item Support partition values not in the array: |
| 491 |
% \end{itemize} |
| 492 |
% |
| 493 |
% \noindent Some implementations of quicksort allow for a partition value $P$ |
| 494 |
% that does not correspond to a value in the array, divding the array |
| 495 |
% into: |
| 496 |
% \begin{eqnarray*}s |
| 497 |
% & A_0 \dots\/A_i , A_{(i+1)} \dots\ A_N & |
| 498 |
% \end{eqnarray*} |
| 499 |
% \noindent where $i$ is arbitrary. This is usually less efficient, as there is |
| 500 |
% an additional value to be sorted with each iteration and hence a |
| 501 |
% greater number of iterations in the best case. |
| 502 |
% |
| 503 |
% In some cases, it is not possible to know the best partition value |
| 504 |
% within an array segment, or a single partition may not be applicable |
| 505 |
% (such as an array containing only two distinct values); however, |
| 506 |
% there may be some knowledge of the array's distribution. In the best |
| 507 |
% case, a pre-calculated median of the array's contents might already be |
| 508 |
% available prior to sorting, which would be the ideal partition value |
| 509 |
% for the first iteration but would be unlikely to be a value in the |
| 510 |
% array, let alone a value of known position. |
| 511 |
% |
| 512 |
% This would likely require significant changes to the algorithm. |
| 513 |
% |
| 514 |
% \ifexcludelongtest\else |
| 515 |
% \section{Large-Scale Sorting} |
| 516 |
% |
| 517 |
% |
| 518 |
% \makeatletter |
| 519 |
% \iffalse |
| 520 |
%<*example> |
| 521 |
% \fi |
| 522 |
\begin{exg}{$\backslash$sortArray on a large |
| 523 |
scale}\begin{LTXexample} |
| 524 |
\newarray{A} |
| 525 |
\expandarrayelementtrue |
| 526 |
\reinitrand[counter=rand,quiet=y] |
| 527 |
\newcommand{\asize}{10000} |
| 528 |
\multido{\i=1+1}{\asize}{ |
| 529 |
\rand |
| 530 |
\A(\i)={\arabic{rand}} |
| 531 |
} |
| 532 |
|
| 533 |
\textbf{Before sort:} |
| 534 |
|
| 535 |
\multido{\i=1+1}{50}{ |
| 536 |
\A(\i) |
| 537 |
}\dots |
| 538 |
|
| 539 |
\sortArray[arraysortcomparenum]{% |
| 540 |
\asize}{A} |
| 541 |
|
| 542 |
\line(1,0){100} |
| 543 |
|
| 544 |
\textbf{After sort:} |
| 545 |
|
| 546 |
\multido{\i=1+1}{50}{ |
| 547 |
\A(\i) |
| 548 |
}\dots |
| 549 |
|
| 550 |
\end{LTXexample} |
| 551 |
This example uses the |multido| and |lcg| packages\end{exg} |
| 552 |
% \iffalse |
| 553 |
%</example> |
| 554 |
% \fi |
| 555 |
% \fi |
| 556 |
% |
| 557 |
% \section{Implementation} |
| 558 |
%\StopEventually{\PrintChanges \pagebreak[4] \PrintIndex} |
| 559 |
% |
| 560 |
% \begin{macro}{\arraysort@extrapkgs} |
| 561 |
% The \LaTeX\ package-option support does not allow conditional |
| 562 |
% includes of packages. So, instead, we build up the required |
| 563 |
% |\RequiresPackage| statements inside the |\arraysort@extrapkgs| |
| 564 |
% macro. |
| 565 |
% \begin{macrocode} |
| 566 |
\newcommand*{\arraysort@extrapkgs}{} |
| 567 |
% \end{macrocode} |
| 568 |
% \end{macro} |
| 569 |
% |
| 570 |
% \begin{macro}{comparestr} |
| 571 |
% \begin{macrocode} |
| 572 |
\DeclareOption{comparestr}{ |
| 573 |
\g@addto@macro{\arraysort@extrapkgs}{ |
| 574 |
\RequirePackage{pdftexcmds}% for comparison. TODO: use compare.sty optionally |
| 575 |
} |
| 576 |
% \end{macrocode} |
| 577 |
% \begin{macro}{\arraysortcomparestr} |
| 578 |
% Called with two arguments, guaranteed to be re-evaluatable. |
| 579 |
% must set arraysortresequal if arguments are considered equal, otherwise |
| 580 |
% must set arraysortresult true if |#2| is to be sorted after |#1|, otherwise |
| 581 |
% must set both flags false. |
| 582 |
% |
| 583 |
% Basic ASCII-like comparison |
| 584 |
% \begin{macrocode} |
| 585 |
\newcommand*{\arraysortcomparestr}[2]{% |
| 586 |
\protected@edef\arraysort@left{#1}% |
| 587 |
\protected@edef\arraysort@right{#2}% |
| 588 |
\arraysort@comparestr% |
| 589 |
} |
| 590 |
% \end{macrocode} |
| 591 |
% |
| 592 |
% The following macro performs the comparison. The parameters must (it |
| 593 |
% seems) be passed by macro as passing by parameter |#1| and |#2| did |
| 594 |
% not cause the expected results, hence the extra macro. |
| 595 |
% \begin{macrocode} |
| 596 |
\newcommand*{\arraysort@comparestr}{% |
| 597 |
\protected@edef\arraysort@compresult{\pdf@strcmp{\arraysort@left}{\arraysort@right}}% |
| 598 |
\ifthenelse{\equal{\arraysort@compresult}{0}}{% |
| 599 |
\toggletrue{arraysortresequal}% |
| 600 |
}{% |
| 601 |
\togglefalse{arraysortresequal}% |
| 602 |
\ifthenelse{\equal{\arraysort@compresult}{-1}}{% |
| 603 |
\toggletrue{arraysortresult}% #2 > #1 |
| 604 |
}{% |
| 605 |
\togglefalse{arraysortresult}% #2 < #1 |
| 606 |
}% |
| 607 |
}% |
| 608 |
} |
| 609 |
} |
| 610 |
% \end{macrocode} |
| 611 |
% \end{macro} |
| 612 |
% \end{macro} |
| 613 |
% \begin{macro}{comparenum} |
| 614 |
% \begin{macrocode} |
| 615 |
% Numeric comparison, as |\arraysortcomparestr| but used with arrays compairng numbers |
| 616 |
\DeclareOption{comparenum}{ |
| 617 |
% \end{macrocode} |
| 618 |
% \begin{macro}{\arraysortcomparenum} |
| 619 |
% \begin{macrocode} |
| 620 |
\newcommand*{\arraysortcomparenum}[2]{% |
| 621 |
\ifthenelse{\equal{#1}{#2}}{% |
| 622 |
\toggletrue{arraysortresequal}% |
| 623 |
}{% |
| 624 |
\togglefalse{arraysortresequal}% |
| 625 |
\ifthenelse{#2 > #1}{% |
| 626 |
\toggletrue{arraysortresult}% |
| 627 |
}{% |
| 628 |
\togglefalse{arraysortresult}% |
| 629 |
}% |
| 630 |
}% |
| 631 |
} |
| 632 |
} |
| 633 |
% \end{macrocode} |
| 634 |
% \end{macro} |
| 635 |
% \end{macro} |
| 636 |
% |
| 637 |
% All partitioning algorithms should complete in O(1) time; that is, |
| 638 |
% they should not iterate over the array, or do anything that takes |
| 639 |
% longer the more elements there are. |
| 640 |
% |
| 641 |
% \begin{macro}{\sortArrayPartitionMed} |
| 642 |
% |
| 643 |
% Partition the segment consisting of indexes |#2|--|#3| (inclusive) |
| 644 |
% of array named |#4|, using comparator |#1| |
| 645 |
% |
| 646 |
% Use the median of the first, last and middle values. While this has |
| 647 |
% extra overhead compared to sortArrayPartitionFirst, it is guaranteed |
| 648 |
% to avoid the worst-case performance of that method. If the array is |
| 649 |
% randomly shuffled prior to sorting, this usually offers the best |
| 650 |
% performance. This is the default method. |
| 651 |
% |
| 652 |
% Performance depends on the comparison macro. |
| 653 |
% |
| 654 |
% May not work well if there are many duplicate values. |
| 655 |
% \begin{macrocode} |
| 656 |
\newcommand*{\sortArrayPartitionMed}[4]{% |
| 657 |
\setcounter{arraysort@temp1}{(#2 + #3) / 2}% |
| 658 |
\edef\arraysort@midpos{\arabic{arraysort@temp1}}% |
| 659 |
\testarray{#4}(#2)\protected@edef\arraysort@left{\temp@macro}% |
| 660 |
\testarray{#4}(\arraysort@midpos)\protected@edef\arraysort@mid{\temp@macro}% |
| 661 |
\testarray{#4}(#3)\protected@edef\arraysort@right{\temp@macro}% |
| 662 |
\csname#1\endcsname{\arraysort@left}{\arraysort@mid}% |
| 663 |
\iftoggle{arraysortresequal}{% |
| 664 |
% \end{macrocode} |
| 665 |
% left $=$ mid |
| 666 |
% if any two are the same, there can be no median, so may as well |
| 667 |
% leave alone |
| 668 |
% \begin{macrocode} |
| 669 |
}{% |
| 670 |
% \end{macrocode} |
| 671 |
% left $\ne$ mid |
| 672 |
% \begin{macrocode} |
| 673 |
\iftoggle{arraysortresult}{% |
| 674 |
% \end{macrocode} |
| 675 |
% left $<$ mid |
| 676 |
% \begin{macrocode} |
| 677 |
\csname#1\endcsname{\arraysort@left}{\arraysort@right}% |
| 678 |
\iftoggle{arraysortresequal}{% |
| 679 |
% \end{macrocode} |
| 680 |
% $(\mbox{left} = \mbox{right}) < \mbox{mid}$ |
| 681 |
% \begin{macrocode} |
| 682 |
}{% |
| 683 |
\iftoggle{arraysortresult}{% |
| 684 |
% \end{macrocode} |
| 685 |
% left $<$ mid, left $<$ right |
| 686 |
% \begin{macrocode} |
| 687 |
\csname#1\endcsname{\arraysort@mid}{\arraysort@right}% |
| 688 |
\iftoggle{arraysortresequal}{% |
| 689 |
% \end{macrocode} |
| 690 |
% $\mbox{left} < (\mbox{mid} = \mbox{right})$ |
| 691 |
% \begin{macrocode} |
| 692 |
}{% |
| 693 |
\iftoggle{arraysortresult}{% |
| 694 |
% \end{macrocode} |
| 695 |
% $\mbox{left} < \mbox{mid} < \mbox{right}$ |
| 696 |
% \begin{macrocode} |
| 697 |
\arraysort@swap{#4}{#2}{\arraysort@midpos}% |
| 698 |
}{% |
| 699 |
% \end{macrocode} |
| 700 |
% $\mbox{left} < \mbox{right} < \mbox{mid}$ |
| 701 |
% \begin{macrocode} |
| 702 |
\arraysort@swap{#4}{#2}{#3}% |
| 703 |
}% |
| 704 |
}% |
| 705 |
}{% |
| 706 |
% \end{macrocode} |
| 707 |
% left $<$ mid, left $>$ right |
| 708 |
% |
| 709 |
% left is already in the middle; leave alone |
| 710 |
% \begin{macrocode} |
| 711 |
}% |
| 712 |
}% |
| 713 |
}{% |
| 714 |
% \end{macrocode} |
| 715 |
% left $>$ mid |
| 716 |
% \begin{macrocode} |
| 717 |
\csname#1\endcsname{\arraysort@mid}{\arraysort@right}% |
| 718 |
\iftoggle{arraysortresequal}{% |
| 719 |
% \end{macrocode} |
| 720 |
% $\mbox{left} > (\mbox{mid} = \mbox{right})$ |
| 721 |
% \begin{macrocode} |
| 722 |
}{% |
| 723 |
\iftoggle{arraysortresult}{% |
| 724 |
% \end{macrocode} |
| 725 |
% $\mbox{left} > \mbox{right} > \mbox{mid}$ |
| 726 |
% \begin{macrocode} |
| 727 |
\arraysort@swap{#4}{#2}{#3}% |
| 728 |
% \end{macrocode} |
| 729 |
% swap right \& left, so left is median |
| 730 |
% \begin{macrocode} |
| 731 |
}{% |
| 732 |
% \end{macrocode} |
| 733 |
% $\mbox{left} > \mbox{mid} > \mbox{right}$ |
| 734 |
% |
| 735 |
% swap right \& mid, so left is median |
| 736 |
% \begin{macrocode} |
| 737 |
\arraysort@swap{#4}{#2}{\arraysort@midpos}% |
| 738 |
}% |
| 739 |
}% |
| 740 |
}% |
| 741 |
}% |
| 742 |
\sortArrayPartitionFirst{#1}{#2}{#3}{#4}% |
| 743 |
} |
| 744 |
% \end{macrocode} |
| 745 |
% |
| 746 |
% \begin{macro}{\sortArrayPartitionRand} |
| 747 |
% |
| 748 |
% Partition the sub-array |
| 749 |
% consisting of indexes |#2|--|#3| (inclusive) of array named |#4|, |
| 750 |
% using comparator |#1| |
| 751 |
% |
| 752 |
% Use the lcg package to generate a (pseudo)-random partition |
| 753 |
% value. This should perform reasonably well most of the time, and you |
| 754 |
% can simply re-run LaTeX if the performance is unacceptable. |
| 755 |
% |
| 756 |
% Caution: this macro will re-initialise the LCG package. |
| 757 |
% \begin{macro}{randompart} |
| 758 |
% \begin{macrocode} |
| 759 |
\DeclareOption{randompart}{ |
| 760 |
\g@addto@macro{\arraysort@extrapkgs}{ |
| 761 |
% \end{macrocode} |
| 762 |
% Store for later execution the fact that we will need tho |lcg| package |
| 763 |
% for random numbers |
| 764 |
% \begin{macrocode} |
| 765 |
\RequirePackage[quiet]{lcg} |
| 766 |
} |
| 767 |
\newcommand*{\sortArrayPartitionRand}[4]{% |
| 768 |
% \end{macrocode} |
| 769 |
% It is necessary to change the start and end values of the sequence; the only way |
| 770 |
% to do this is by reinitialising |lcg|. There are 2 possible |
| 771 |
% problems; firstly, reinitrand outputs whitespace; and secondly it |
| 772 |
% prints out a warning about a re-used counter. It's actually best to re-use |
| 773 |
% the counter, but there's no way to silence the warning. |
| 774 |
% \begin{macrocode} |
| 775 |
\reinitrand[counter=arraysort@temp1,first=#2,last=#3,quiet=y]% |
| 776 |
\rand% |
| 777 |
\arraysort@swap{#4}{#2}{\arabic{arraysort@temp1}}% |
| 778 |
\sortArrayPartitionFirst{#1}{#2}{#3}{#4}% |
| 779 |
} |
| 780 |
} |
| 781 |
% \end{macrocode} |
| 782 |
% \end{macro} |
| 783 |
% \end{macro} |
| 784 |
% |
| 785 |
% \begin{macro}{\sortArrayPartitionMid} |
| 786 |
% |
| 787 |
% Partition the sub-array |
| 788 |
% consisting of indexes |#2|--|#3| (inclusive) of array named |#4|, |
| 789 |
% using comparator |#1| |
| 790 |
% |
| 791 |
% This implementation uses the middle value in the array segment. This is |
| 792 |
% generally the best option if you don't know anything about the |
| 793 |
% array's contents; in particular, it offers reasonable speed when |
| 794 |
% attempting to re-sort previously-sorted ararys. |
| 795 |
% \begin{macrocode} |
| 796 |
\newcommand*{\sortArrayPartitionMid}[4]{% |
| 797 |
\setcounter{arraysort@temp1}{(#2 + #3) / 2}% |
| 798 |
\arraysort@swap{#4}{#2}{\arabic{arraysort@temp1}}% |
| 799 |
\sortArrayPartitionFirst{#1}{#2}{#3}{#4}% |
| 800 |
} |
| 801 |
% \end{macrocode} |
| 802 |
% \end{macro} |
| 803 |
% |
| 804 |
% \begin{macro}{\sortArrayPartitionFirst} |
| 805 |
% Partition the array segment |
| 806 |
% consisting of indexes |#2|--|#3| (inclusive) of array named |#4|, |
| 807 |
% using comparator |#1| |
| 808 |
% |
| 809 |
% This implementation uses the first value in the array segment. This is |
| 810 |
% fastest in theory, but only if the array is pre-shuffled. This has |
| 811 |
% the worst performance when attempting to sort an already-sorted |
| 812 |
% array. |
| 813 |
% \begin{macrocode} |
| 814 |
\newcommand*{\sortArrayPartitionFirst}[4]{% |
| 815 |
\setcounter{arraysort@partpos}{#2}% |
| 816 |
\setcounter{arraysort@temp1}{#2 + 1}% |
| 817 |
\setcounter{arraysort@endpos}{#3 + 1}% |
| 818 |
\arraysort@repeats{arraysort@temp1}{\value{arraysort@temp1}}{\value{arraysort@endpos}}{1}{% |
| 819 |
\testarray{#4}(\arabic{arraysort@temp1})% |
| 820 |
% \end{macrocode} |
| 821 |
% if the value $A_{\mbox{temp1}}$ is less than partition $A_P$, |
| 822 |
% decrement the partition counter by 1 and swap. |
| 823 |
% |
| 824 |
% |\let| copies without expanding: |
| 825 |
% \begin{macrocode} |
| 826 |
\let\arraysort@cur\temp@macro% |
| 827 |
\testarray{#4}(\arabic{arraysort@partpos})% |
| 828 |
% \end{macrocode} |
| 829 |
% Expand the macros only once just in case they would be different |
| 830 |
% on subsequent expansion: |
| 831 |
% \begin{macrocode} |
| 832 |
\protected@edef\arraysort@left{\arraysort@cur}% |
| 833 |
\protected@edef\arraysort@right{\temp@macro}% |
| 834 |
\csname#1\endcsname{\arraysort@left}{\arraysort@right}% #2 = cur, #3 = partition |
| 835 |
\setcounter{arraysort@temp2}{\value{arraysort@partpos} + 1}% |
| 836 |
\iftoggle{arraysortresequal}{% #2 = #3 |
| 837 |
% \end{macrocode} |
| 838 |
% Must be moved before pivot |
| 839 |
% Swap $A_P$ with $A_{P+1}$ then swap (the new) $A_P$ with |
| 840 |
% current ($A_{\mbox{temp2}}=A_{P+1}$) |
| 841 |
% \begin{macrocode} |
| 842 |
\arraysort@swap{#4}{\arabic{arraysort@partpos}}{\arabic{arraysort@temp2}}% |
| 843 |
\arraysort@swap{#4}{\arabic{arraysort@partpos}}{\arabic{arraysort@temp1}}% |
| 844 |
% \end{macrocode} |
| 845 |
% Increment partition; otherwise the next non-equal pivot will break |
| 846 |
% \begin{macrocode} |
| 847 |
\stepcounter{arraysort@partpos}% |
| 848 |
}{% |
| 849 |
\iftoggle{arraysortresult}{% #3 > #2 |
| 850 |
\ifthenelse{\equal{\arabic{arraysort@temp2}}{\arabic{arraysort@temp1}}}{% |
| 851 |
% \end{macrocode} |
| 852 |
% Just swap part with current value; they are adjacent |
| 853 |
% \begin{macrocode} |
| 854 |
\arraysort@swap{#4}{\arabic{arraysort@partpos}}{\arabic{arraysort@temp1}}% |
| 855 |
}{% |
| 856 |
% \end{macrocode} |
| 857 |
% Swap $A_P$ with $A_{P+1}$ then swap (the new) $A_P$ with |
| 858 |
% current ($\mbox{temp}_2=A_{p+1}$) |
| 859 |
% \begin{macrocode} |
| 860 |
\arraysort@swap{#4}{\arabic{arraysort@partpos}}{\arabic{arraysort@temp2}}% |
| 861 |
\arraysort@swap{#4}{\arabic{arraysort@partpos}}{\arabic{arraysort@temp1}}% |
| 862 |
}% |
| 863 |
% \end{macrocode} |
| 864 |
% Increment partition; one more in left array segment |
| 865 |
% \begin{macrocode} |
| 866 |
\stepcounter{arraysort@partpos}% |
| 867 |
}{% |
| 868 |
% \end{macrocode} |
| 869 |
% $A_{|arraysort@cur|} > A_P$ and already after it; leave it alone |
| 870 |
% \begin{macrocode} |
| 871 |
}% |
| 872 |
}% |
| 873 |
}% |
| 874 |
} |
| 875 |
% \end{macrocode} |
| 876 |
% \end{macro} |
| 877 |
% |
| 878 |
% \begin{macro}{\ProcessOptions} |
| 879 |
% This processes the package include options, defining whichever of |
| 880 |
% the above macros the user has asked for, and adding a list of any |
| 881 |
% optional packages into |\arraysort@extrapkgs|. |
| 882 |
% |
| 883 |
% \begin{macrocode} |
| 884 |
\ProcessOptions\relax |
| 885 |
% \end{macrocode} |
| 886 |
%\end{macro} |
| 887 |
% |
| 888 |
% Package includes for required packages: |
| 889 |
% |
| 890 |
% For loading the arrays that we will sort |
| 891 |
% \begin{macrocode} |
| 892 |
\RequirePackage{arrayjobx} |
| 893 |
% \end{macrocode} |
| 894 |
% For easier syntax on counter operations |
| 895 |
% \begin{macrocode} |
| 896 |
\RequirePackage{calc} |
| 897 |
% \end{macrocode} |
| 898 |
% For comparisons |
| 899 |
% \begin{macrocode} |
| 900 |
\RequirePackage{ifthen} |
| 901 |
% \end{macrocode} |
| 902 |
% Toggles etc. |
| 903 |
% \begin{macrocode} |
| 904 |
\RequirePackage{etoolbox} |
| 905 |
% \end{macrocode} |
| 906 |
% To declare macros with multiple optional arguments (\textit{ie} |
| 907 |
% |\sortArray|) |
| 908 |
% \begin{macrocode} |
| 909 |
\RequirePackage{xargs} |
| 910 |
% \end{macrocode} |
| 911 |
% For partitioning |
| 912 |
% \begin{macrocode} |
| 913 |
\RequirePackage{macroswap} |
| 914 |
% \end{macrocode} |
| 915 |
% now process any conditional includes |
| 916 |
% \begin{macrocode} |
| 917 |
\arraysort@extrapkgs |
| 918 |
% \end{macrocode} |
| 919 |
% |
| 920 |
% Now we are done including packages, so discard the macro: |
| 921 |
% \begin{macrocode} |
| 922 |
\let\arraysort@extrapkgs\relax |
| 923 |
% \end{macrocode} |
| 924 |
% |
| 925 |
% |
| 926 |
% \DescribeMacro{\sortArray} |
| 927 |
% Sort the elements at index |#2|--|#3| of array named |#4|, using |
| 928 |
% comparator |#1|. |
| 929 |
% |
| 930 |
% |#5| is the partitioning algorithm to use. |
| 931 |
% |
| 932 |
% \textit{eg} |\sortArray[1]{3}{ABC}| |
| 933 |
% |
| 934 |
% Defined using the |xargs| package |
| 935 |
% \begin{macrocode} |
| 936 |
\newcommandx*\sortArray[5][1=arraysortcomparestr,2=1,5=sortArrayPartitionMed]{% |
| 937 |
\ifcsname#1\endcsname% |
| 938 |
\ifthenelse{#2>0}{% |
| 939 |
\ifthenelse{#3>#2}{% |
| 940 |
\ifcsname total@#4\endcsname% |
| 941 |
\arraysort@sort{#1}{#2}{#3}{#4}{#5}% |
| 942 |
\else% |
| 943 |
\PackageError{arraysort}{Cannot sort unknown array #4}{}% |
| 944 |
\fi% |
| 945 |
}{% |
| 946 |
\PackageError{arraysort}{Cannot sort; to index #3 greater than from index #2}{}% |
| 947 |
}% |
| 948 |
}{% |
| 949 |
\PackageError{arraysort}{Cannot sort; Invalid from index #2}{}% |
| 950 |
}% |
| 951 |
\else% |
| 952 |
\PackageError{arraysort}{Cannot sort by undefined comparator #1}{}% |
| 953 |
\fi% |
| 954 |
} |
| 955 |
% \end{macrocode} |
| 956 |
% \end{macro} |
| 957 |
% |
| 958 |
% \begin{macro}{\arraysort@sort} |
| 959 |
% As |\sortArray|, except that it doesn't validate its parameters, |
| 960 |
% hence the |@| in the name (signifying an internal macro). |
| 961 |
% |
| 962 |
% Use with caution as error messages may be misleading. |
| 963 |
% |
| 964 |
% Sort the elements at index |#2|--|#3| of array named |#4|, using |
| 965 |
% comparator |#1| |
| 966 |
% |
| 967 |
% |#5| is the partitioning algorithm to use. |
| 968 |
% \begin{macrocode} |
| 969 |
\newcommand*{\arraysort@sort}[5]{% |
| 970 |
\csname#5\endcsname{#1}{#2}{#3}{#4}% |
| 971 |
% \end{macrocode} |
| 972 |
% Keep the position on the local stack! |
| 973 |
% \begin{macrocode} |
| 974 |
\edef\arraysort@partition{\value{arraysort@partpos}}% |
| 975 |
\setcounter{arraysort@temp1}{\arraysort@partition - 1}% |
| 976 |
\ifthenelse{#2 = \value{arraysort@temp1} \OR #2 > \value{arraysort@temp1}}{% |
| 977 |
}{% |
| 978 |
\edef\arraysort@to{\arabic{arraysort@temp1}}% |
| 979 |
\arraysort@sort{#1}{#2}{\arraysort@to}{#4}{#5}% |
| 980 |
}% |
| 981 |
\setcounter{arraysort@temp1}{\arraysort@partition + 1}% |
| 982 |
\ifthenelse{\value{arraysort@temp1} = #3 \OR #3 < \value{arraysort@temp1}}{% |
| 983 |
}{% |
| 984 |
\edef\arraysort@from{\arabic{arraysort@temp1}}% |
| 985 |
\arraysort@sort{#1}{\arraysort@from}{#3}{#4}{#5}% |
| 986 |
}% |
| 987 |
} |
| 988 |
% \end{macrocode} |
| 989 |
% \end{macro} |
| 990 |
% |
| 991 |
% |
| 992 |
% Counters used for sorting |
| 993 |
% |
| 994 |
% current position of the partition |
| 995 |
% \begin{macrocode} |
| 996 |
\newcounter{arraysort@partpos} |
| 997 |
% \end{macrocode} |
| 998 |
% current position in loop |
| 999 |
% \begin{macrocode} |
| 1000 |
\newcounter{arraysort@temp1} |
| 1001 |
% \end{macrocode} |
| 1002 |
% partition position $+1$ |
| 1003 |
% \begin{macrocode} |
| 1004 |
\newcounter{arraysort@temp2} |
| 1005 |
% \end{macrocode} |
| 1006 |
% used for partitioning |
| 1007 |
% \begin{macrocode} |
| 1008 |
\newcounter{arraysort@endpos} |
| 1009 |
% \end{macrocode} |
| 1010 |
% |
| 1011 |
% Toggles used by the comparator macro |
| 1012 |
% |
| 1013 |
% set by comparison if $|#1| < |#2|$ |
| 1014 |
% \begin{macrocode} |
| 1015 |
\newtoggle{arraysortresult} |
| 1016 |
% \end{macrocode} |
| 1017 |
% set by comparison if $|#1| = |#2|$ |
| 1018 |
% \begin{macrocode} |
| 1019 |
\newtoggle{arraysortresequal} |
| 1020 |
% \end{macrocode} |
| 1021 |
% |
| 1022 |
% \begin{macro}{\arrayort@repeats} |
| 1023 |
% |
| 1024 |
% Don't use |\whiledo| here because it uses up TeX's capacity, |
| 1025 |
% so rolling own basic repeat loop... |
| 1026 |
% |
| 1027 |
% For counter |#1| from |#2| to |#3| step |#4|, do |#5| |
| 1028 |
% \begin{macrocode} |
| 1029 |
\newcommand*{\arraysort@repeats}[5]{% |
| 1030 |
\setcounter{#1}{#2}% |
| 1031 |
\ifthenelse{\equal{\value{#1}}{#3}}{% |
| 1032 |
}{% |
| 1033 |
#5% |
| 1034 |
\addtocounter{#1}{#4}% |
| 1035 |
\arraysort@repeats{#1}{\arabic{#1}}{#3}{#4}{#5}% |
| 1036 |
}% |
| 1037 |
} |
| 1038 |
% \end{macrocode} |
| 1039 |
% \end{macro} |
| 1040 |
% |
| 1041 |
% \begin{macro}{\arraysort@swap} |
| 1042 |
% Globally swap array values |#1(#2)| with |#1(#3)| |
| 1043 |
% |
| 1044 |
% \textit{ie} \\ |#1| is the macro name \\ |
| 1045 |
% |#2| and |#3| are the numeic indexes of the array elements to be |
| 1046 |
% swapped. |
| 1047 |
% \begin{macrocode} |
| 1048 |
\newcommand\arraysort@swap[3]{% |
| 1049 |
% \end{macrocode} |
| 1050 |
% |arrayjobx| does not provide a way to assign an array element to the |
| 1051 |
% contents of another element (or macro) without expanding it. This macro simply |
| 1052 |
% swaps the definitions of the two macros used internally by |arrayjobx|: |
| 1053 |
% \begin{macrocode} |
| 1054 |
\gmacroswap{#1#2\string~}{#1#3\string~}% |
| 1055 |
} |
| 1056 |
% \end{macrocode} |
| 1057 |
% \end{macro} |
| 1058 |
% |
| 1059 |
% That is all |
| 1060 |
% \Finale |
| 1061 |
\endinput |