Take the 2-minute tour ×
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.

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

2 Answers 2

up vote 6 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.

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

\pagestyle{empty}

% as we are going to compare non integral values we need xintfrac and
% not only xint.
\usepackage{xintfrac}

\usepackage{tikz}
% Styles defined by Tom Bombaldi. (modified: all share the same size)
\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=\bf, yshift=1.5mm},
        b/.style={minimum width=6mm, minimum height=6mm, rounded corners=1.5mm, draw=black, fill=magenta!50!black, text=white, font=\bf},
        g/.style={minimum width=6mm, minimum height=6mm, rounded corners=1.5mm, draw=black, fill=gray, text=white, font=\bf}}


% This code is copied from the xint pdf documentation (1.09e or later)
% and adapted to use the Tom Bombaldi's TikZ styles rather than just colored
% boxes as in the original.

\def\QSMore  #1#2{\xintifGt {#2}{#1}{{#2}}{ }}% space will be gobbled 
\def\QSEqual #1#2{\xintifEq {#2}{#1}{{#2}}{ }}
\def\QSLess  #1#2{\xintifLt {#2}{#1}{{#2}}{ }}
%
\makeatletter
\def\QS@a #1{\expandafter \QS@b \expandafter {\xintLength {#1}}{#1}}
\def\QS@b #1{\ifcase #1
                      \expandafter\QS@empty
                   \or\expandafter\QS@single
                 \else\expandafter\QS@c
                 \fi
}%
\def\QS@empty  #1{}
\def\QS@single #1{\QSIr {#1}}

\def\QS@c #1{\expandafter\QS@e\expandafter 
                   {\romannumeral0\xintnthelt {-1}{#1}}{#1}%
}%

\def\QS@e #1#2{\expandafter\QS@f\expandafter
                   {\romannumeral0\xintapplyunbraced {\QSMore  {#1}}{#2}}%
                   {\romannumeral0\xintapplyunbraced {\QSEqual {#1}}{#2}}%
                   {\romannumeral0\xintapplyunbraced {\QSLess  {#1}}{#2}}%
}%

\def\QS@f #1#2#3{\expandafter\QS@g\expandafter {#2}{#3}{#1}}%
% Here \QSLr, \QSIr, \QSr have been let to \relax, so expansion stops.
% #2= elements < pivot, #1 = elements = pivot, #3 = elements > pivot
\def\QS@g #1#2#3{\QSLr {#2}\QSIr {#1}\QSRr {#3}}%
%

% ADAPTED FROM THE ORIGINAL TO USE TIKZ
\newcounter{cellcount}
% AND STOP AUTOMATICALLY
\newcounter{pivotcount}

\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}%
      \xintifForFirst {\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};}%
}

% adapted to work with a comma separated list on input
% 

\def\QSinitialize #1{\edef\tmp{\xintCSVtoList{#1}}%
    \expandafter\def\expandafter\QS@list\expandafter
                     {\expandafter\QSRr\expandafter {\tmp}}%
    \let\QSRr\DecoRIGHT
    \par\centerline{\rule[1.5mm]{0pt}{8mm}\setcounter{cellcount}{0}%
                \begin{tikzpicture}\QS@list\end{tikzpicture}}
}

% from the original code, with changes to highlight the chosen pivot
% also after it has been moved.

\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}}
}

\def\QSsortStep {\def\QSLr {\noexpand\QS@a}% 
                 \def\QSRr {\noexpand\QS@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}}
}


\makeatother

\begin{document}\thispagestyle{empty}

%% starting with xintfrac 1.09f or later, spaces do not matter, but in
%% case people have an older version, I do not put any spaces here in
%% the comma separated list.

\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

%% starting with xintfrac 1.09f or later, spaces do not matter, but in
%% case people have an older version, I do not put any spaces here in
%% the comma separated list.

\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}

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
1  
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.