我正在尝试对仅包含几个元素的数组进行可视化快速排序。我不确定如何在 TikZ 中执行此操作。
我想创建这样的东西：
有什么建议吗？
答案1
可以让TeX快速排序自动进行，如下图所示xint pdf 文档我从该参考资料中摘取了代码，(*) 做了一些修改，并tikz从中窃取了代码汤姆·邦巴尔迪的回答。
2015 年的更新内容如下：
考虑到
xinttools现在需要明确加载，添加一些解释并改进代码，
还提供了一种更快的替代代码，尽管差异只会显示数百个值，这使得它在这种情况下有点不相关。
(*) 文档中的代码xint.pdf目前正在更新，与本次更新同时进行。
\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}
代码的缺点是每次比较都要进行三次。这可能听起来令人惊讶，但请记住，我们还没有将项目转换为数组状结构，这样每个项目都可以轻松单独访问。因此，代码将列表复制三份，第一个副本用于解析小于枢轴值的元素，第二个副本用于解析等于枢轴值的元素，第三个副本用于解析大于枢轴值的元素。
这是一种替代方法，它只进行一次数值比较，但仍然不会将数据转换为结构化数组。
% 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
第二个例子：
答案2
首先，我为不同类型的盒子创建了五种样式（Lime、Olive、Raised、Big、Grayed）。绘制盒子的命令采用以下形式的列表：计数/样式并绘制数数给定列表中的元素风格然后前进到下一个。
代码
\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}
输出
