21

In Introduction to Algorithms, by Thomas Cormen, there are some algorithm like in this image. With one column for the code, one for the cost and one for the times.

I searched a lot, but I didn't find how to do it.

enter image description here

3
  • 1
    I suspect this was done with 3 columns, no rows (other than heading and body), in a tabular, one of the standard algorithm packages in the code column, and forced linebreaks in the cost and times columns. But that is a guess. Apr 21, 2015 at 2:36
  • 2
    I guess Cormen did use the clrscode package, since he mentions: This document describes how to use the clrscode package in LaTeX2ε to typeset pseudocode in the style of Introduction to Algorithms, Second edition, by Cormen, Leiserson, Rivest, and Stein (CLRS) Apr 21, 2015 at 8:35
  • Using \> is mentioned in the manual of clrscode
    – egreg
    Apr 21, 2015 at 16:23

3 Answers 3

16

This is what I'd do, if I were not to use clrscode.

\documentclass[11pt]{article}

\usepackage[noend]{algorithmic}

\newcommand{\TITLE}[1]{\item[#1]}
\renewcommand{\algorithmiccomment}[1]{$/\!/$ \parbox[t]{4.5cm}{\raggedright #1}}
% ugly hack for for/while
\newbox\fixbox
\renewcommand{\algorithmicdo}{\setbox\fixbox\hbox{\ {} }\hskip-\wd\fixbox}
% end of hack
\newcommand{\algcost}[2]{\strut\hfill\makebox[1.5cm][l]{#1}\makebox[4cm][l]{#2}}

\begin{document}
\begin{algorithmic}[1]
  \TITLE{\textsc{Insertion-Sort}$(A)$}
    \algcost{\textit{cost}}{\textit{times}}
  \FOR{$j=2$ \TO $A.\mathit{length}$
    \algcost{$c_1$}{$n$}}
  \STATE $\mathit{key} = A[j]$
    \algcost{$c_2$}{$n-1$}
  \STATE \COMMENT{Insert $A[j]$ to the sorted sequence $A[1..j-1]$}
    \algcost{$0$}{$n-1$}
  \STATE $i = j-1$
    \algcost{$c_4$}{$n-1$}
  \WHILE{$i>0$ \AND $A[i]>key$
    \algcost{$c_5$}{$\sum_{j=2}^{n} t_j$}}
  \STATE $A[i+1]= A[i]$
    \algcost{$c_6$}{$\sum_{j=2}^{n} (t_j-1)$}
  \STATE $i = i-1$
    \algcost{$c_7$}{$\sum_{j=2}^{n} (t_j-1)$}
  \ENDWHILE
  \STATE $A[i+1] = \mathit{key}$
    \algcost{$c_8$}{$n-1$}
  \ENDFOR
\end{algorithmic}
\end{document}

Please, notice a few things:

  1. There are three widths (in centimeters) that may need tweaking.

  2. The costs of for and while statements are inside the brackets and there must not be any space between them and the closing bracket. This is a bit fragile. The same for if and all other block statements.

  3. The cost of line 3 is displayed next to the first of the two lines, not the second (as in the original). It was easier like this, but I think I also prefer it.

This answer takes the opposite route from Jubobs's answer, which is using the clrscode package. If you prefer to use clrscode, I'm sure you'll find the way to properly use |> for tabbing the extra columns, although it's not well documented. Also, it may be preferable for other reasons too, if you want your algorithms to look exactly like those in the book.


result

1
  • Pretty nicely done.
    – jub0bs
    Apr 21, 2015 at 22:47
10

(Only a partial answer)

Cormen used his clrscode package for the second edition of CLRS, but a "beefed-up" version of it, called clrscode3e, for the third edition, from which the Insertion Sort algorithm in your screenshot is taken. For more details, see this.

The code for typesetting the algorithm (but without the "cost" and "times" columns) can be found on page 6 of the clrscode3e documentation. The latter makes no mention of how to typeset columns. Besides, the package's source code doesn't seem to provide any (undocumented) mechanism for that.

However, Cormen's codebox environment is based on a tabbing environment; perhaps there is something to be done there, but I'm not that familiar with tabbing...

enter image description here

\documentclass{article}

\usepackage{clrscode3e}

\begin{document}

\begin{codebox}
\Procname{$\proc{Insertion-Sort}(A)$}
\li \For $j \gets 2$ \To $\attrib{A}{length}$
\li     \Do
            $\id{key} \gets A[j]$
\li         \Comment Insert $A[j]$ into the sorted sequence
                $A[1 \twodots j-1]$.
\li         $i \gets j-1$
\li         \While $i > 0$ and $A[i] > \id{key}$
\li             \Do
                    $A[i + 1] = A[i]$
\li                 $i \gets i-1$
                \End
\li         $A[i+1] \gets \id{key}$
        \End
\end{codebox}

\end{document}
3
  • 1
    Do you know which package is used for the fourth edition ?
    – alper
    Aug 18, 2022 at 20:21
  • @alper I'm only learning now, thanks to your comment, that a 4th edition has been released! Thanks. So no, I don't know yet what they use in the new one.
    – jub0bs
    Aug 18, 2022 at 20:55
  • I belive the algorithms are same but mainly they add some colors
    – alper
    Aug 19, 2022 at 8:47
2

There is the CLRS package, code name "clrscode3e", the description of the package as well as the .sty file are available in the web-site: http://www.cs.dartmouth.edu/~thc/clrscode/, you can easily download the .sty file and also read the description.

\documentclass{article}

\usepackage{clrscode3e}

\begin{document}

\begin{codebox}
\Procname{$\proc{Insertion-Sort}(A)$}
\li \For $j \gets 2$ \To $\attrib{A}{length}$
\li     \Do
            $\id{key} \gets A[j]$
\li         \Comment Insert $A[j]$ into the sorted sequence
                $A[1 \twodots j-1]$.
\li         $i \gets j-1$
\li         \While $i > 0$ and $A[i] > \id{key}$
\li             \Do
                    $A[i + 1] = A[i]$
\li                 $i \gets i-1$
                \End
\li         $A[i+1] \gets \id{key}$
        \End
\end{codebox}
\end{document}

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .