[Tex/LaTex] How to 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.

---