4

Can anyone recommend any tutorial/library or just explain how can I draw this type of table, divided into few part with arrows? Like on this picture:

enter image description here

  • I would be inclined to do this with the TiKZ package, using its matrix library, in conjunction with the shapes.multipart library. – Alan Munn Oct 26 '13 at 19:56
  • 1
    The title should be "Representing a sorting algorithm for lists". No ? – projetmbc Oct 26 '13 at 20:50
  • @projetmbc Good call. That yields a related question: Typesetting Sorting Diagrams – Alan Munn Oct 26 '13 at 21:10
  • 1
    @ziva The question I linked to has an example very much like yours, so if you play around with that and then run into problems you can edit your question to get more specific help. – Alan Munn Oct 26 '13 at 21:18
  • 1
    @AlanMunn The question does, but the answer does not. Therefore I'm quite against calling it a duplicate (since duplicates have to be answered, which is essentially not the case here). – yo' Oct 26 '13 at 21:23
2

This solution uses the following packages:

  • forest (also etoolbox)

    forest is used to create the upper part of the tree, every node of this tree will use the algorithm behind the sort key. Every mirrored node will be placed at the orthogonal opposite of the last line. The edges of the lower part are rudimentary drawn with an edge path operator of TikZ (forest offers a few options for edges that are not used here).

  • l3sort

    The very first example of the l3sort manual is directly used here to sort the integers of a node.

  • xstring

    The xstring package provides a \StrSubstitute macro that first replaces all spaces to commas , for the l3sort macro. The sorted result is then again thrown into \StrSubstitute to re-replace the commas to spaces.

Furthermore, the calc library from TikZ is used to place the sorted nodes at the other side (this could have been easily done without calc) as well as the PGFmath function strrepeat.

A similar approach for a calc-less positioning can be found in another answer of mine (look for Stern Brocot at and Stern Brocot at*). This is also the answer where I first used the strrepeat function.

This function is only used once to automatically create the name of the first child of the last level of the tree (here: 39) so that it can be used later as \forestOnes.
The sort level key also sets up the \forestSortLevel macro so that it can be used inside the sort key.

Possible improvements

  • Getting the maximum level directly from forest and not from the user.
  • Sorting with spaces without the need to replace the spaces (or maybe a LaTeX3 solution for the replacing).
  • Automatic splitting of a list of numbers by forest so that one does only need to add the root node.
  • Exploiting something like execute at end picture but for forest for the lower part of the tree. The sort key is actually executed before anything is drawn (and outside of TikZ) which is the reason that all \nodes (and their edges) are saved in \myNodes. The same is true for the \coordinate call which just as well should be setup by sort level.

Code

\documentclass[tikz]{standalone}
\usepackage{forest,l3sort,xstring}
\usetikzlibrary{calc}
\makeatletter
\pgfmathdeclarefunction{strrepeat}{2}{%
  \begingroup\pgfmathint{#2}\pgfmath@count\pgfmathresult
    \let\pgfmathresult\pgfutil@empty
    \pgfutil@loop\ifnum\pgfmath@count>0\relax
      \expandafter\def\expandafter\pgfmathresult\expandafter{\pgfmathresult#1}%
      \advance\pgfmath@count-1\relax
    \pgfutil@repeat\pgfmath@smuggleone\pgfmathresult\endgroup}
\makeatother
\def\myNodes{}
\ExplSyntaxOn
\newcommand*\sortList[1]{%
  \clist_sort:Nn#1{\int_compare:nNnTF{##1}>{##2}\sort_reversed:\sort_ordered:}}
\ExplSyntaxOff
\forestset{
  sort/.code={%
    \pgfmathparse{level()>\forestSortLevel}%
    \ifnum\pgfmathresult=0
      \StrSubstitute{\forestov{content}}{ }{,}[\myList]%
      \sortList\myList
      \StrSubstitute{\myList}{,}{ }[\myList]%
      \pgfmathparse{strrepeat("1",level())}%
      \xappto\myNodes{\noexpand\node at ($(\forestov{name}|-m)!-1!(\forestov{name})$)
        (m\forestov{name}) {\myList}}%
      \pgfmathparse{level()==\forestSortLevel}%
      \ifnum\pgfmathresult=1
        \forestOget{\forestov{@first}}{name}\forestFirst
        \forestOget{\forestov{@last}}{name}\forestLast
        \xappto\myNodes{{[<-]edge (\forestOv{\forestov{@first}}{name})
          \ifx\forestFirst\forestLast\else edge (\forestOv{\forestov{@last}}{name})\fi}}%
      \fi
      \ifnum\forestov{@parent}=0\else
        \xappto\myNodes{edge (m\forestOv{\forestov{@parent}}{name})}%
      \fi
      \gappto\myNodes{;}%
    \fi}}
\forestset{sort level/.code=%
  \pgfmathparse{#1}\let\forestSortLevel\pgfmathresult
  \pgfmathparse{strrepeat("1",\forestSortLevel+1)}\let\forestOnes\pgfmathresult}
\begin{document}
\begin{forest} 
  /tikz/arrows=->, /tikz/>=latex, %/tikz/nodes={draw},
  for tree={delay={sort}}, sort level=2
[38 27 43 3 9 82 10
  [38 27 43 3
    [38 27 [39][27]]
    [43 3 [43][3]]
  ]
  [9 82 10
    [9 82 [9] [82]]
    [10 [10]]
  ]
]
%
\coordinate (m) at (!|-!\forestOnes);
\myNodes
\end{forest}
\end{document}

Output

enter image description here

  • \sort_ordered: and \sort_reversed: are deprecated as of 2018-12-31; the right functions are \sort_return_same: and \sort_return_swapped: – egreg Dec 27 '18 at 22:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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