TeX - LaTeX Stack Exchange is a question and answer site for users of TeX, LaTeX, ConTeXt, and related typesetting systems. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:

enter image description here

Suggestions?

share|improve this question

migrated from stackoverflow.com Oct 28 '13 at 6:18

This question came from our site for professional and enthusiast programmers.

    
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
up vote 12 down vote accepted

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

quicksort1

Second example:

quicksort2

share|improve this answer
    
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... – jfbu Nov 6 '13 at 18:25
2  
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 ;-) – jfbu Nov 6 '13 at 18:28
    
that is beautiful. thank you very much. – rhl Nov 7 '13 at 19:04

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}

Output

enter image description here

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.