16

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

  • 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. – Lyndon White Apr 21 '15 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) – TonioElGringo Apr 21 '15 at 8:35
  • Using \> is mentioned in the manual of clrscode – egreg Apr 21 '15 at 16:23
11

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

  • Pretty nicely done. – jubobs Apr 21 '15 at 22:47
7

(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}
0

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}

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.