17

While revisiting some old notes on algorithms, I came across a code snippet illustrating the sorting of a vector using quicksort.

I’m dissatisfied with how the nodes are defined relative to each other, requiring some nodes to be repeated to maintain references. Additionally, I had to draw them in reverse order to ensure the edges overlapped correctly.

One potential optimization I considered is ensuring the "examining" styled node always displays \(i\) above it.

How can I optimize the code to avoid repetition?

a page

% arara: pdflatex % arara: latexmk: { clean: partial } \documentclass[tikz, border=.2cm]{standalone} \usetikzlibrary{positioning} \tikzset{ vector/.style = { draw = black, rectangle, align = center, anchor = west, fill = yellow!40, font = \ttfamily\bfseries, minimum height = 0.7cm, minimum size = 0.7cm }, label/.style = { node distance = 0pt, font = \scriptsize, }, % cells styles undiscovered/.style = { fill = teal!20, draw = teal, dashed, }, examining/.style = { very thick, fill=teal!50, }, pivot/.style = { fill = purple!60, }, smallerPivot/.style = { fill = red!20, }, greaterPivot/.style = { fill = gray!20, draw = gray!80, dashed, }, } \begin{document} \begin{tikzpicture} \node[vector, undiscovered] (11) {13}; \node[vector, left=-1pt of 11, undiscovered] (10) {25}; \node[vector, left=-1pt of 10, undiscovered] (9) {21}; \node[vector, left=-1pt of 9, undiscovered] (8) {30}; \node[vector, left=-1pt of 8, undiscovered] (7) {12}; \node[vector, left=-1pt of 7, undiscovered] (6) {27}; \node[vector, left=-1pt of 6, undiscovered] (5) {15}; \node[vector, left=-1pt of 5, undiscovered] (4) {29}; \node[vector, left=-1pt of 4, undiscovered] (3) {28}; \node[vector, left=-1pt of 3, examining] (2) {14}; \node[vector, left=-1pt of 2, pivot] (1) {20}; % NOTE I have to repeat it otherwise I don't have the reference to node 2 for node 1 \node[vector, right=-1pt of 1, examining] (2) {14}; \node[label, above=of 2] (index-i) {\(i\)}; \node[label, below=of 1] (index-j) {\(j\)}; \end{tikzpicture} \begin{tikzpicture} \node[vector, undiscovered] (11) {13}; \node[vector, left=-1pt of 11, undiscovered] (10) {25}; \node[vector, left=-1pt of 10, undiscovered] (9) {21}; \node[vector, left=-1pt of 9, undiscovered] (8) {30}; \node[vector, left=-1pt of 8, undiscovered] (7) {12}; \node[vector, left=-1pt of 7, undiscovered] (6) {27}; \node[vector, left=-1pt of 6, undiscovered] (5) {15}; \node[vector, left=-1pt of 5, undiscovered] (4) {29}; \node[vector, left=-1pt of 3, smallerPivot] (2) {14}; \node[vector, right=-1pt of 2, examining] (3) {28}; \node[vector, left=-1pt of 2, pivot] (1) {20}; \node[label, above=of 3] (index-i) {\(i\)}; \node[label, below=of 2] (index-j) {\(j\)}; \end{tikzpicture} \begin{tikzpicture} \node[vector, undiscovered] (11) {13}; \node[vector, left=-1pt of 11, undiscovered] (10) {25}; \node[vector, left=-1pt of 10, undiscovered] (9) {21}; \node[vector, left=-1pt of 9, undiscovered] (8) {30}; \node[vector, left=-1pt of 8, undiscovered] (7) {12}; \node[vector, left=-1pt of 7, undiscovered] (6) {27}; \node[vector, left=-1pt of 6, undiscovered] (5) {15}; \node[vector, left=-1pt of 4, greaterPivot] (3) {28}; \node[vector, right=-1pt of 3, examining] (4) {29}; \node[vector, left=-1pt of 3, smallerPivot] (2) {14}; \node[vector, left=-1pt of 2, pivot] (1) {20}; \node[label, above=of 4] (index-i) {\(i\)}; \node[label, below=of 2] (index-j) {\(j\)}; \end{tikzpicture} \begin{tikzpicture} \node[vector, undiscovered] (11) {13}; \node[vector, left=-1pt of 11, undiscovered] (10) {25}; \node[vector, left=-1pt of 10, undiscovered] (9) {21}; \node[vector, left=-1pt of 9, undiscovered] (8) {30}; \node[vector, left=-1pt of 8, undiscovered] (7) {12}; \node[vector, left=-1pt of 7, undiscovered] (6) {27}; \node[vector, left=-1pt of 5, greaterPivot] (4) {29}; \node[vector, right=-1pt of 4, examining] (5) {15}; \node[vector, left=-1pt of 4, greaterPivot] (3) {28}; \node[vector, left=-1pt of 3, smallerPivot] (2) {14}; \node[vector, left=-1pt of 2, pivot] (1) {20}; \node[label, above=of 5] (index-i) {\(i\)}; \node[label, below=of 2] (index-j) {\(j\)}; \end{tikzpicture} \begin{tikzpicture} \node[vector, undiscovered] (11) {13}; \node[vector, left=-1pt of 11, undiscovered] (10) {25}; \node[vector, left=-1pt of 10, undiscovered] (9) {21}; \node[vector, left=-1pt of 9, undiscovered] (8) {30}; \node[vector, left=-1pt of 8, undiscovered] (7) {12}; \node[vector, left=-1pt of 6, greaterPivot] (5) {28}; \node[vector, right=-1pt of 5, examining] (6) {27}; \node[vector, left=-1pt of 5, greaterPivot] (4) {29}; \node[vector, left=-1pt of 4, smallerPivot] (3) {15}; \node[vector, left=-1pt of 3, smallerPivot] (2) {14}; \node[vector, left=-1pt of 2, pivot] (1) {20}; \node[label, above=of 6] (index-i) {\(i\)}; \node[label, below=of 3] (index-j) {\(j\)}; \end{tikzpicture} \begin{tikzpicture} \node[vector, undiscovered] (11) {13}; \node[vector, left=-1pt of 11, undiscovered] (10) {25}; \node[vector, left=-1pt of 10, undiscovered] (9) {21}; \node[vector, left=-1pt of 9, undiscovered] (8) {30}; \node[vector, left=-1pt of 7, greaterPivot] (6) {27}; \node[vector, right=-1pt of 6, examining] (7) {12}; \node[vector, left=-1pt of 6, greaterPivot] (5) {28}; \node[vector, left=-1pt of 5, greaterPivot] (4) {29}; \node[vector, left=-1pt of 4, smallerPivot] (3) {15}; \node[vector, left=-1pt of 3, smallerPivot] (2) {14}; \node[vector, left=-1pt of 2, pivot] (1) {20}; \node[label, above=of 7] (index-i) {\(i\)}; \node[label, below=of 3] (index-j) {\(j\)}; \end{tikzpicture} \begin{tikzpicture} \node[vector, undiscovered] (11) {13}; \node[vector, left=-1pt of 11, undiscovered] (10) {25}; \node[vector, left=-1pt of 10, undiscovered] (9) {21}; \node[vector, left=-1pt of 8, greaterPivot] (7) {29}; \node[vector, right=-1pt of 7, examining] (8) {30}; \node[vector, left=-1pt of 7, greaterPivot] (6) {27}; \node[vector, left=-1pt of 6, greaterPivot] (5) {28}; \node[vector, left=-1pt of 5, smallerPivot] (4) {12}; \node[vector, left=-1pt of 4, smallerPivot] (3) {15}; \node[vector, left=-1pt of 3, smallerPivot] (2) {14}; \node[vector, left=-1pt of 2, pivot] (1) {20}; \node[label, above=of 8] (index-i) {\(i\)}; \node[label, below=of 4] (index-j) {\(j\)}; \end{tikzpicture} \begin{tikzpicture} \node[vector, undiscovered] (11) {13}; \node[vector, left=-1pt of 11, undiscovered] (10) {25}; \node[vector, left=-1pt of 9, greaterPivot] (8) {30}; \node[vector, right=-1pt of 8, examining] (9) {21}; \node[vector, left=-1pt of 8, greaterPivot] (7) {29}; \node[vector, left=-1pt of 7, greaterPivot] (6) {27}; \node[vector, left=-1pt of 6, greaterPivot] (5) {28}; \node[vector, left=-1pt of 5, smallerPivot] (4) {12}; \node[vector, left=-1pt of 4, smallerPivot] (3) {15}; \node[vector, left=-1pt of 3, smallerPivot] (2) {14}; \node[vector, left=-1pt of 2, pivot] (1) {20}; \node[label, above=of 9] (index-i) {\(i\)}; \node[label, below=of 4] (index-j) {\(j\)}; \end{tikzpicture} \begin{tikzpicture} \node[vector, undiscovered] (11) {13}; \node[vector, left=-1pt of 10, greaterPivot] (9) {21}; \node[vector, right=-1pt of 9, examining] (10) {25}; \node[vector, left=-1pt of 9, greaterPivot] (8) {30}; \node[vector, left=-1pt of 8, greaterPivot] (7) {29}; \node[vector, left=-1pt of 7, greaterPivot] (6) {27}; \node[vector, left=-1pt of 6, greaterPivot] (5) {28}; \node[vector, left=-1pt of 5, smallerPivot] (4) {12}; \node[vector, left=-1pt of 4, smallerPivot] (3) {15}; \node[vector, left=-1pt of 3, smallerPivot] (2) {14}; \node[vector, left=-1pt of 2, pivot] (1) {20}; \node[label, above=of 10] (index-i) {\(i\)}; \node[label, below=of 4] (index-j) {\(j\)}; \end{tikzpicture} \begin{tikzpicture} \node[vector, greaterPivot] (10) {25}; \node[vector, right=-1pt of 10, examining] (11) {13}; \node[vector, left=-1pt of 10, greaterPivot] (9) {21}; \node[vector, left=-1pt of 9, greaterPivot] (8) {30}; \node[vector, left=-1pt of 8, greaterPivot] (7) {29}; \node[vector, left=-1pt of 7, greaterPivot] (6) {27}; \node[vector, left=-1pt of 6, greaterPivot] (5) {28}; \node[vector, left=-1pt of 5, smallerPivot] (4) {12}; \node[vector, left=-1pt of 4, smallerPivot] (3) {15}; \node[vector, left=-1pt of 3, smallerPivot] (2) {14}; \node[vector, left=-1pt of 2, pivot] (1) {20}; \node[label, above=of 11] (index-i) {\(i\)}; \node[label, below=of 4] (index-j) {\(j\)}; \end{tikzpicture} \begin{tikzpicture} \node[vector, greaterPivot] (11) {28}; \node[vector, left=-1pt of 11, greaterPivot] (10) {25}; \node[vector, left=-1pt of 10, greaterPivot] (9) {21}; \node[vector, left=-1pt of 9, greaterPivot] (8) {30}; \node[vector, left=-1pt of 8, greaterPivot] (7) {29}; \node[vector, left=-1pt of 7, greaterPivot] (6) {27}; \node[vector, left=-1pt of 6, smallerPivot] (5) {13}; \node[vector, left=-1pt of 5, smallerPivot] (4) {12}; \node[vector, left=-1pt of 4, smallerPivot] (3) {15}; \node[vector, left=-1pt of 3, smallerPivot] (2) {14}; \node[vector, left=-1pt of 2, pivot] (1) {20}; \node[label, above=of 11] (index-i) {\phantom{\(i\)}}; \node[label, below=of 5] (index-j) {\(j\)}; \end{tikzpicture} \begin{tikzpicture} \node[vector, greaterPivot] (11) {28}; \node[vector, left=-1pt of 11, greaterPivot] (10) {25}; \node[vector, left=-1pt of 10, greaterPivot] (9) {21}; \node[vector, left=-1pt of 9, greaterPivot] (8) {30}; \node[vector, left=-1pt of 8, greaterPivot] (7) {29}; \node[vector, left=-1pt of 7, greaterPivot] (6) {27}; \node[vector, left=-1pt of 6, pivot] (5) {20}; \node[vector, left=-1pt of 5, smallerPivot] (4) {12}; \node[vector, left=-1pt of 4, smallerPivot] (3) {15}; \node[vector, left=-1pt of 3, smallerPivot] (2) {14}; \node[vector, left=-1pt of 2, smallerPivot] (1) {13}; \node[label, above=of 11] (index-i) {\phantom{\(i\)}}; \node[label, below=of 5] (index-j) {\(j\)}; \end{tikzpicture} \end{document}
Improve this question
9
  • 2
    Instead of changing the order in which you draw them, you could use layers to put elements in the foreground. Commented Jan 22 at 15:13
  • 1
    Personally I'd use a tikz matrix to place the nodes next to each other and the overlay-beamer-styles tikz library to highlight different nodes on different overlays. This way you would only need one copy of the code. (if you need the result in another class, you could then include it as image) Commented Jan 22 at 15:16
  • 2
    Hmm... I would try to parameterize it in a pgffor-loop, and I wouldn't worry too much about optimization for such a small data-set. Do you intent to use a larger data set? Can you please share a bit of your motivation to optimize? @samcarter_is_at_topanswers.xyz's mention of overlay sounds interesting. Commented Jan 22 at 15:44
  • 2
    @samcarter_is_at_topanswers.xyz Hm, since either the positions of the nodes or their content change, many things would be dependent on the overlay number. I don't know if it will be that easy. Commented Jan 22 at 16:18
  • 1
    My reason for optimizing is that I would like to write cleaner and more concise code. Since I used this method throughout all the notes for drawing vectors of numbers, I think a solution with a TikZ matrix and layers, as suggested by @samcarter_is_at_topanswers.xyz, would be optimal for my scenario. Commented Jan 22 at 18:11

1 Answer 1

Reset to default
21
+50

While I suggested creating an algorithm that does the sorting itself and returns the results for each step, the drawing can be made much easier without that.

  • Placing all nodes on one path allows us to use in front of path (the default) and behind path to place the dashed nodes behind the others.

  • The chains library with an outer sep of zero is used which places the nodes line-on-line. This allows a comfortable placement of the nodes in a loop.

  • The mandatory argment for \QuickSortStep is a list. Its entries consist of a control character (J, j, x, u, <, >) and the actual value. The control character is used for a shortcut style that applies the proper keys.

    • It looks like the examining node is also the one with the i which is why x also places the i.
    • There seems to be two cases where the j is needed: for the pivot (J) and for a smallerPivot (j).
    • p is for the pivot and
    • u is for the unexamined while
    • < and > stand for smaller and greater than pivot.

  • The bb correction key makes sure that the picture/path has always the same bounding box. This is very much on the safe side.

    In case the i or the j is missing we add an invisible node of the same size in the picture. The horizontal can change due to the line-width choices of the first and last node. Here, a correction is included that depends on very thick. (Alternatively, we can use trim left=(chain-begin.west), trim right=(chain-end.east).)

    More intricate solutions exists, this is just a very easy and short way to implement this.

The code can be used with the standalone class as well as the beamer class with the overlay options. For this, the mode key exists which has three choices:

  • standalone places a step as its own TikZ picture.

  • beamer only places the path for the step but not a TikZ picture. This means that \QuickSortStep must be used inside a TikZ picture.

    The \QuickSortStep accepts an optional overlay specification which is used in place of the default + one, i.e. \QuickSortStep<4>{…}.

  • animate which also places the step as its own TikZ picture but issues a \newframe if another \QuickSortStep follows directly (without an empty line between them). You can still use \newframe et al. on your own.

You can also use mode = standalone in beamer and animate for more control.

The \path<…> overlay specification syntax is very basic since it doesn't prevent the “jumping” of a diagram. It really should be more advanced in my opinion. The library overlay-beamer-styles of the CTAN package aobs-tikz does help in many cases flawlessly but in this predictable case it is not necessary.

Code

common

In the examples below, the following code is saved as 735598-quicksort.tex.

\usetikzlibrary{chains} \makeatletter \newcommand*\QuickSortAnimatePossibleFrameX{\@ifnextchar\QuickSortStep{\newframe}{}} \makeatother \newcommand*\tikzqsset{\pgfqkeys{/tikz/qs}} \tikzqsset{ dashed/.style={% depending on the size of the node (7mm) dash phase=1.5mm, dash pattern=on 3mm off 1mm on 2mm off 1mm, % dash phase=-1mm, dash pattern=on 1mm off 1mm on 1mm off 1mm on 1mm off 2mm, }, vector/.style = {shape=rectangle, font = \ttfamily\bfseries, draw = black, fill = yellow!40, minimum size = +0.7cm, outer sep = +0pt}, label/.style = {node distance = 0pt,font = \scriptsize}, % /tikz/label exists already % cells styles undiscovered/.style = {fill = teal!20, draw = teal, qs/dashed}, examining/.style = {fill = teal!50, very thick}, pivot/.style = {fill = purple!60}, smallerPivot/.style = {fill = red!20}, greaterPivot/.style = {fill = gray!20, draw = gray!80, qs/dashed}, % mode/.is choice, mode/standalone/.code=\let\QuickSortAnimatePossibleFrame\relax\def\QuickSortPath##1##2{\tikz\path##2 [qs/bb correction];}, mode/beamer/.code=\let\QuickSortAnimatePossibleFrame\relax\def\QuickSortPath##1##2{\path<##1>##2 [qs/bb correction];}, mode/animate/.code=% \let\QuickSortAnimatePossibleFrame\QuickSortAnimatePossibleFrameX \def\QuickSortPath##1##2{\tikz\path##2 [qs/bb correction];}, mode=standalone, % default, safe to use everywhere bb correction/.style={ insert path={% fake labels to pad vertical size node also[label={[qs/label, path only]above:\phantom{$i$}}, label={[qs/label,path only]below:\phantom{$j$}}](chain-begin) ([xshift=+-.6pt]chain-begin.west)([xshift=+.6pt]chain-end.east)}}, % .6pt half of very thick linewidth parse/.style args={#1#2}{qs/sc-#1/.try, node contents={#2}}, sc-x/.style={in front of path, qs/examining, label=[qs/label]above:$i$}, sc-u/.style={behind path, qs/undiscovered}, sc-j/.style={in front of path, qs/smallerPivot, label=[qs/label]below:$j$}, sc-J/.style={in front of path, qs/pivot, label=[qs/label]below:$j$}, sc-p/.style={in front of path, qs/pivot}, sc->/.style={behind path, qs/greaterPivot}, sc-</.style={in front of path, qs/smallerPivot} } \NewDocumentCommand{\QuickSortStep}{D<>{+} O{} m}{% \begingroup\tikzqsset{#2}% \QuickSortPath{#1}{% [node distance=+0pt, start chain=going right] foreach[count=\i] \v in {#3}{ node[on chain, qs/vector, qs/parse/.expand once=\v]}}% \endgroup\QuickSortAnimatePossibleFrame}

standalone

\documentclass[tikz, border=.2cm]{standalone} \input{735598-quicksort} \begin{document} \QuickSortStep{J20, x14, u28, u29, u15, u27, u12, u30, u21, u25, u13} \QuickSortStep{p20, j14, x28, u29, u15, u27, u12, u30, u21, u25, u13} \QuickSortStep{p20, j14, >28, x29, u15, u27, u12, u30, u21, u25, u13} \QuickSortStep{p20, j14, >28, >29, x15, u27, u12, u30, u21, u25, u13} \QuickSortStep{p20, <14, j15, >29, >28, x27, u12, u30, u21, u25, u13} \QuickSortStep{p20, <14, j15, >29, >28, >27, x12, u30, u21, u25, u13} \QuickSortStep{p20, <14, <15, j12, >28, >27, >29, x30, u21, u25, u13} \QuickSortStep{p20, <14, <15, j12, >28, >27, >29, >30, x21, u25, u13} \QuickSortStep{p20, <14, <15, j12, >28, >27, >29, >30, >21, x25, u13} \QuickSortStep{p20, <14, <15, j12, >28, >27, >29, >30, >21, >25, x13} \QuickSortStep{p20, <14, <15, <12, j13, >27, >29, >30, >21, >25, >28} \QuickSortStep{<13, <14, <15, <12, J20, >27, >29, >30, >21, >25, >28} \end{document}

beamer

\documentclass[t]{beamer} \usepackage{tikz} \input{735598-quicksort} \tikzqsset{mode=beamer} \begin{document} \begin{frame} \begin{tikzpicture} \QuickSortStep{J20, x14, u28, u29, u15, u27, u12, u30, u21, u25, u13} \QuickSortStep{p20, j14, x28, u29, u15, u27, u12, u30, u21, u25, u13} \QuickSortStep{p20, j14, >28, x29, u15, u27, u12, u30, u21, u25, u13} \QuickSortStep{p20, j14, >28, >29, x15, u27, u12, u30, u21, u25, u13} \QuickSortStep{p20, <14, j15, >29, >28, x27, u12, u30, u21, u25, u13} \QuickSortStep{p20, <14, j15, >29, >28, >27, x12, u30, u21, u25, u13} \QuickSortStep{p20, <14, <15, j12, >28, >27, >29, x30, u21, u25, u13} \QuickSortStep{p20, <14, <15, j12, >28, >27, >29, >30, x21, u25, u13} \QuickSortStep{p20, <14, <15, j12, >28, >27, >29, >30, >21, x25, u13} \QuickSortStep{p20, <14, <15, j12, >28, >27, >29, >30, >21, >25, x13} \QuickSortStep{p20, <14, <15, <12, j13, >27, >29, >30, >21, >25, >28} \QuickSortStep{<13, <14, <15, <12, J20, >27, >29, >30, >21, >25, >28} \end{tikzpicture} \end{frame} \end{document}

animate

\documentclass{article} \usepackage{animate, tikz} \input{735598-quicksort} \tikzqsset{mode=animate} \begin{document} \begin{animateinline}[controls=all]{5} \QuickSortStep{J20, x14, u28, u29, u15, u27, u12, u30, u21, u25, u13} \QuickSortStep{p20, j14, x28, u29, u15, u27, u12, u30, u21, u25, u13} \QuickSortStep{p20, j14, >28, x29, u15, u27, u12, u30, u21, u25, u13} \QuickSortStep{p20, j14, >28, >29, x15, u27, u12, u30, u21, u25, u13} % new paragraph (= empty line) not good for smart-ish test \QuickSortStep{p20, <14, j15, >29, >28, x27, u12, u30, u21, u25, u13} \QuickSortStep{p20, <14, j15, >29, >28, >27, x12, u30, u21, u25, u13} \QuickSortStep{p20, <14, <15, j12, >28, >27, >29, x30, u21, u25, u13} \QuickSortStep{p20, <14, <15, j12, >28, >27, >29, >30, x21, u25, u13} \QuickSortStep{p20, <14, <15, j12, >28, >27, >29, >30, >21, x25, u13} \QuickSortStep{p20, <14, <15, j12, >28, >27, >29, >30, >21, >25, x13} % \QuickSortStep{p20, <14, <15, <12, j13, >27, >29, >30, >21, >25, >28} % \QuickSortStep{<13, <14, <15, <12, J20, >27, >29, >30, >21, >25, >28} \end{animateinline} \end{document}

Output

enter image description here

Improve this answer
9
  • 3
    I genuinely don't know what to say. I'm truly astonished. Commented Jan 22 at 21:11
  • 1
    I wouldn’t be able to replicate your work; to me, it’s truly a form of art. However, I did notice a very slight shift on the Beamer slides. Commented Jan 22 at 21:26
  • 1
    @EmanueleNardi Indeed, when the i is missing my bb correction isn't enough. Let me take a look. The font size is different is why this is happening. Commented Jan 22 at 21:40
  • 1
    @EmanueleNardi It's no problem. I selected to remove the other beamer option. It should really be always the inline one (now named beamer). I've also added another note about animate. A more complex solution would involve a syntax like \QuickSortSteps{{<step 1>}, {<step 2>}, {<step 3>}, {<step 4>}, …} (i.e. a list of lists). Commented Jan 22 at 21:56
  • 1
    @EmanueleNardi See update. I've placed the common code in another file and \input that in the preamble. There's no need to have that code in three times. Commented Jan 23 at 18:32

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.