How can I typeset an algorithm with columns as in CLRS (Introduction to Algorithms)?

Question

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.

Answer 1

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.

---

Answer 2

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

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

Answer 3

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}