# What are the Easiest/Cleanest way to create arrays for illustrating quicksort with tikz?

I am trying to visualize quicksort on an array with just a few elements. I am not sure of how to do this in TikZ.

I want to create something like this:

Suggestions?

• Welcome to TeX.SX! Your post was migrated here from Stack Overflow. Please register on this site, too, and make sure that both accounts are associated with each other (by using the same OpenID), otherwise you won't be able to comment on or accept answers or edit your question. – Qrrbrbirlbel Oct 28 '13 at 6:52
• Looks like something for the chains library with a few exceptional nodes that have a greater size or are shifted upwards. – Qrrbrbirlbel Oct 28 '13 at 6:54
• Related question. Pretty lists for sorting algorithms – Alan Munn Nov 3 '13 at 1:10

It is possible to let TeX do automatically the quicksort, as is illustrated in the xint pdf documentation. I pick up the code from that reference,(*) with some adaptations, and steal the tikz code from Tom Bombaldi's answer.

The 2015 update is to:

1. take into account that xinttools now needs to be explicitely loaded,

2. add some explanations and improve the code,

3. also provide an alternative faster code, although the difference would show up only with hundreds of values, which makes it somewhat irrelevant in this context.

(*) The code in the xint.pdf documentation is currently being updated, simultaneously to this update.

\documentclass{scrartcl}
\usepackage[margin=10mm]{geometry}
\renewcommand*\familydefault{\sfdefault}
\usepackage[T1]{fontenc}

%----------------------------------------------------
% USAGE:
% \QSinitialize{comma, separated, numerical, values}
% \loop
% \QSpivotStep
% \ifnum\value{pivotcount}>0
%   \QSsortStep
% \repeat
%----------------------------------------------------

% xintfrac does not load xinttools, this must be done explicitely if needed as here.
\usepackage{xintfrac, xinttools}

\usepackage{tikz}

%----------------------------------------------------------------
% FIRST PART: TikZ styles and macros for the actual drawing
\newcounter{cellcount}%  used for coordinates of the node
\newcounter{pivotcount}% when it will remain at zero, will signal the sort is finished.

% Styles defined by Tom Bombaldi. (modified: all share the same size)
% (re-modified \bf -> \bfseries due to extremely annoying warnings from
% KOMA-script which are truly a pain and do not make any sense regarding \bf:
% if I want to use \bf, and know what I am doing, why should I get HARASSED
% by police of LaTeX good conduct ? )
\tikzset{l/.style={minimum width=6mm, minimum height=6mm, rounded corners=1.5mm, draw=black, fill=lime!70!gray},
o/.style={minimum width=6mm, minimum height=6mm, rounded corners=1.5mm, draw=black, fill=olive!50},
r/.style={minimum width=6mm, minimum height=6mm, rounded corners=1.5mm, draw=black, fill=magenta!50!black, text=white, font=\bfseries, yshift=1.5mm},
% this is the "b" style as used in the image below
%        b/.style={minimum width=6mm, minimum height=6mm, rounded corners=1.5mm, draw=black, fill=magenta!50!black, text=white, font=\bfseries},
% nicer:
b/.style={minimum width=6mm, minimum height=6mm, rounded corners=1.5mm, draw=black, fill=white, text=magenta!50!black, font=\bfseries},
g/.style={minimum width=6mm, minimum height=6mm, rounded corners=1.5mm, draw=black, fill=gray, text=white, font=\bfseries}}

% NOTE the b style was originally the same as the r(aised) style apart from
% not being raised, but I find it nicer with a somewhat different
% specification. I have not updated the images though.

% How the nodes are drawn depending on whether on the left of the pivot value
% or on the right, or is a pivot value, or a raised pivot during selection phase.

\def\DecoLEFT #1{%
\xintFor* ##1 in {#1} \do
{\stepcounter{cellcount}\node[o] at (\arabic{cellcount},0) {##1};}%
}

\def\DecoINERT #1{%
\xintFor* ##1 in {#1} \do
{\stepcounter{cellcount}\node[g] at (\arabic{cellcount},0) {##1};}%
}

\def\DecoRIGHT #1{%
\xintFor* ##1 in {#1} \do
{\stepcounter{cellcount}\node[l] at (\arabic{cellcount},0) {##1};}%
}

\def\DecoLEFTwithPivot #1{\stepcounter{pivotcount}%
\xintFor* ##1 in {#1} \do
{\stepcounter{cellcount}%
\xintifForLast {\node[r]}{\node[o]} at (\arabic{cellcount},0) {##1};}%
}

\def\DecoINERTwithPivot #1{\stepcounter{pivotcount}%
\xintFor* ##1 in {#1} \do
{\stepcounter{cellcount}%
\xintifForLast {\node[b]}{\node[g]} at (\arabic{cellcount},0) {##1};}%
}

\def\DecoRIGHTwithPivot #1{\stepcounter{pivotcount}%
\xintFor* ##1 in {#1} \do
{\stepcounter{cellcount}%
\xintifForLast {\node[r]}{\node[l]} at (\arabic{cellcount},0) {##1};}%
}

%----------------------------------------------------------------
% SECOND PART: the actual sorting routines.

\makeatletter
\def\QS@sort@a #1{\expandafter \QS@sort@b \expandafter {\xintLength {#1}}{#1}}
\def\QS@sort@b #1{\ifcase #1
\expandafter\QS@sort@empty
\or\expandafter\QS@sort@single
\else\expandafter\QS@sort@c
\fi
}%
\def\QS@sort@empty  #1{}
\def\QS@sort@single #1{\QSIr {#1}}

% This step is to pick the last as pivot.
\def\QS@sort@c #1%
{\expandafter\QS@sort@d\expandafter {\romannumeral0\xintnthelt {-1}{#1}}{#1}}%

% Here \QSLr, \QSIr, \QSr have been let to \relax.
% The trick with \xintApplyUnbraced is that for example when selecting
% the elements smaller than pivot, if we had been using \xintApply we
% would have had at the minimum an empty brace pair. Thus we use the
% "unbraced" variant, but then the \QS@select@smaller has added in
% anticipation a level of braces.
\def\QS@sort@d #1#2{%
\QSLr {\xintApplyUnbraced {\QS@select@smaller  {#1}}{#2}}%
\QSIr {\xintApplyUnbraced {\QS@select@equal    {#1}}{#2}}%
\QSRr {\xintApplyUnbraced {\QS@select@greater {#1}}{#2}}%
}%
\def\QS@select@smaller #1#2{\xintifLt {#2}{#1}{{#2}}{ }}% space will stop a f-expansion
\def\QS@select@equal   #1#2{\xintifEq {#2}{#1}{{#2}}{ }}% space will stop a f-expansion
\def\QS@select@greater #1#2{\xintifGt {#2}{#1}{{#2}}{ }}% space will stop a f-expansion

\makeatother
%
% NOTE 1: thus, each comparison with the pivot is done three (!) times.
%
% NOTE 2: we may well end up with \QSLr {<empty>} situations. THis is handled
% silently by the \xintFor loops, and also when \QSLr becomes \QS@sort@a, the
% latter must handle correctly an empty argument.

%----------------------------------------------------------------
% THIRD PART: the main macros \QSpivotStep, \QSsortStep and \QSinitialize.

\makeatletter
% This draws all with suitable highlighting for the newly chosen pivots
% (which will be shown raised)
\def\QSpivotStep {\let\QSLr\DecoLEFTwithPivot
\let\QSIr\DecoINERT
\let\QSIrr\DecoINERT
\let\QSRr\DecoRIGHTwithPivot
\par\centerline{\rule[1.5mm]{0pt}{8mm}%
\setcounter{cellcount}{0}\setcounter{pivotcount}{0}%
\begin{tikzpicture}\QS@list\end{tikzpicture}}
}

% This sorts and then draws, showing where the pivot chosen in the previous
% step go. Next time they will have become "inert". If pivotcount is still at
% zero on exit from \QSpivotStep, then this is the signal to stop before
% executing \QSsortStep.
\def\QSsortStep {\def\QSLr {\noexpand\QS@sort@a}%
\def\QSRr {\noexpand\QS@sort@a}%
\def\QSIr {\noexpand\QSIrr}%
\let\QSIrr\relax
\edef\QS@list{\QS@list}%
\let\QSLr\relax
\let\QSRr\relax
\let\QSIr\relax
\edef\QS@list{\QS@list}%
\let\QSLr\DecoLEFT
\let\QSIr\DecoINERTwithPivot
\let\QSIrr\DecoINERT
\let\QSRr\DecoRIGHT
\par\centerline{\rule[1.5mm]{0pt}{8mm}%
\setcounter{cellcount}{0}%
\begin{tikzpicture}\QS@list\end{tikzpicture}}
}

\def\QSinitialize #1{%
% first, we convert the comma separated values into a list of braced items
% we use an \edef, and anyhow many \edef's will be used later
\edef\QS@list {\noexpand\QSRr {\xintCSVtoList {#1}}}%
\let\QSRr\DecoRIGHT
% The \QSRr marker mutated to draw the last element as
% pivot and the earlier ones with the suitable style.
%
% The list of marked braced items \QS@list is used both for drawing
% (as here) and for doing the exchange of elements during sort.
\par\centerline{\rule[1.5mm]{0pt}{8mm}\setcounter{cellcount}{0}%
\begin{tikzpicture}\QS@list\end{tikzpicture}}
}

\makeatother

\begin{document}

\QSinitialize{5, 3, 9, 8, 7, 2, 4, 1, 6, 5}

\textbf{Step 1:} Choose a pivot

\QSpivotStep
\smallskip

\textbf{Step 2:} Lesser values go to the left, equal or greater values go to the right

\QSsortStep
\smallskip

\textbf{Step 3:} Repeat step 1 with the two sub lists

\QSpivotStep
\smallskip

\textbf{Step 4:} Repeat step 2 with the sub lists:

\QSsortStep
\smallskip

\textbf{Step 5:} and again and again!

\loop
\QSpivotStep
\ifnum\value{pivotcount}>0
\QSsortStep
\repeat

\clearpage

\QSinitialize {1.3, 1.1, 0.7, 1.6, 0.6, 0.9, 0.8, 0.2, 0.1, 1.9,
1.0, 0.5, 0.3, 1.5, 1.8, 2.0, 1.7, 0.4, 1.2, 1.4}

\textbf{Step 1:} Choose a pivot

\QSpivotStep
\smallskip

\textbf{Step 2:} Lesser values go to the left, equal or greater values go to the right

\QSsortStep
\smallskip

\textbf{Step 3:} Repeat step 1 with the two sub lists

\QSpivotStep
\smallskip

\textbf{Step 4:} Repeat step 2 with the sub lists:

\QSsortStep
\smallskip

\textbf{Step 5:} and again and again!

\loop
\QSpivotStep
\ifnum\value{pivotcount}>0
\QSsortStep
\repeat

\end{document}


The code has the drawback of doing each comparison thrice. This may sound surprising but recall we have not converted the items into an array-like structure where each one can be easily individually accessed. Thus the code triplicates the list, and the first copy is parsed for elements less than the pivot value, the second for elements equal to the pivot value, the third for elements greater than the pivot value.

Here is an alternative which will do each numerical comparison only once, still not converting the data into a structured array.

% THIS REPLACES ENTIRELY THE "SECOND PART":
\makeatletter
%
% argument #1 will never be empty
\def\QS@cmp@a #1{\noexpand\QS@sep@A
\expandafter\QS@cmp@d
\expandafter{\romannumeral0\xintnthelt{-1}{#1}}#1??}%
\def\QS@cmp@d  #1#2{\ifx ?#2\expandafter\QS@cmp@done\fi
\xintifCmp {#1}{#2}\tw@\@ne\z@{#2}\QS@cmp@d {#1}}
\def\QS@cmp@done #1?{?}
%
\def\QS@sep@A #1?{\QSLr\QS@sep@L #1\thr@@?#1\thr@@?#1\thr@@?}
\def\QS@sep@L #1#2%
{\ifcase #1{#2}\or\or\else\expandafter\QS@sep@I@start\fi \QS@sep@L}
\def\QS@sep@I@start\QS@sep@L {\noexpand\empty?\QSIr\QS@sep@I}
\def\QS@sep@I #1#2%
{\ifcase#1\or{#2}\or\else\expandafter\QS@sep@R@start\fi\QS@sep@I}
\def\QS@sep@R@start\QS@sep@I {\noexpand\empty?\QSRr\QS@sep@R}
\def\QS@sep@R #1#2%
{\ifcase#1\or\or{#2}\else\expandafter\QS@sep@done\fi\QS@sep@R}
\def\QS@sep@done\QS@sep@R {\noexpand\empty?}
\makeatother

% IN THIRD PART, NEW DEFINITION FOR \QSsortStep (other things not modified)
\makeatletter
\def\QSsortStep {%
\def\QSLr {\QS@cmp@a}\def\QSRr {\QS@cmp@a}%
\def\QSIr {\QSIrr}\let\QSIrr\relax
\edef\QS@list{\QS@list}% compare
\let\QSLr\relax\let\QSRr\relax\let\QSIr\relax
\edef\QS@list{\QS@list}% separate
\def\QSLr ##1##2?{\ifx\empty##1\else\noexpand \QSLr {{##1}##2}\fi}%
\def\QSIr ##1##2?{\ifx\empty##1\else\noexpand \QSIr {{##1}##2}\fi}%
\def\QSRr ##1##2?{\ifx\empty##1\else\noexpand \QSRr {{##1}##2}\fi}%
\edef\QS@list{\QS@list}% gather
\let\QSLr\DecoLEFT \let\QSRr\DecoRIGHT
\let\QSIr\DecoINERTwithPivot \let\QSIrr\DecoINERT
\par\centerline{\rule[1.5mm]{0pt}{8mm}%
\setcounter{cellcount}{0}%
\begin{tikzpicture}\QS@list\end{tikzpicture}}
}%
%
\makeatother


Second example:

• Wahhh, thieves! Oh wait, very nice result ;-D – Tom Bombadil Nov 6 '13 at 18:22
• @TomBombadil nice styles by the way! :) as I modified in two of them some dimensions, perhaps I can copyright them under my name... – user4686 Nov 6 '13 at 18:25
• I'd be veeery careful here, "rectangle with rounded corners" made Samsung pay Apple a billion dollars... – Tom Bombadil Nov 6 '13 at 18:27
• @TomBombadil let's see what my lawyer(s) say ;-) – user4686 Nov 6 '13 at 18:28
• In the first image, for the 5, the old code of 2013 had a bug as it put the other 5 to the right. With the code updated in 2015, the pivot 5 correctly remains to the right of the other 5 which was initially to its left: this is a stable sort. I have not updated the image. (nota bene: I think I did it on purpose back then as the "bug" is in the image of the OP) – user4686 Nov 21 '15 at 23:11

First I created five styles for the different kinds of boxes that there are (Lime, Olive, Raised, Big, Grayed). The command for drawing the boxed then takes a list of the form count/style and draws count elements from the also given list in the given style and then advances to the next.

## Code

\documentclass{scrartcl}
\usepackage[margin=15mm]{geometry}
\usepackage{tikz}
\usepackage{xifthen}
\usepackage{paratype}
\renewcommand*\familydefault{\sfdefault}
\usepackage[T1]{fontenc}

\begin{document}

\newcommand{\boxstring}[2]% numbers, specifications
{   \begin{tikzpicture}
[ l/.style={minimum width=6mm, minimum height=6mm, rounded corners=1.5mm, draw=black, fill=lime!70!gray},
o/.style={minimum width=6mm, minimum height=6mm, rounded corners=1.5mm, draw=black, fill=olive!50},
r/.style={minimum width=6mm, minimum height=6mm, rounded corners=1.5mm, draw=black, fill=magenta!50!black, text=white, font=\bf, yshift=1.5mm},
b/.style={minimum width=8mm, minimum height=8mm, rounded corners=2mm, draw=black, fill=magenta!50!black, text=white, font=\bf},
g/.style={minimum width=8mm, minimum height=8mm, rounded corners=2mm, draw=black, fill=gray, text=white, font=\bf},
]
\xdef\maxindex{0}
\foreach \rep/\opt in {#2}
{   \pgfmathtruncatemacro{\maxin}{\maxindex+\rep}
\xdef\minindex{\maxindex}
\xdef\maxindex{\maxin}
\foreach \x [count=\c] in {#1}
{   \pgfmathtruncatemacro{\drawbool}{and(\c>\minindex,\c<=\maxindex) ? 1 : 0}
\ifthenelse{\drawbool=1}
{   \node[\opt] at (\c,0) {\x};
}{}
}
}
\end{tikzpicture}
\bigskip
}

\textbf{Step 1:} Choose a pivot

\boxstring{5,3,9,8,7,2,4,1,6,5}{9/l,1/r}

\textbf{Step 2:} Lesser values go to the left, equal or greater values go to the right

\boxstring{3,2,4,1,5,5,9,8,7,6}{4/o,1/b,5/l}

\textbf{Step 3:} Repeat from step 1 with the two sub lists

\boxstring{3,2,4,1,5,5,9,8,7,6}{3/o,1/r,1/g,4/l,1/r}

\end{document}