  \input{format1.tex}
  \input{intro1.tex}

\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais]{babel}


\begin{document}

\noindent \Large {\bf Université d'Orléans} \hfill {\bf Maîtrise d'Informatique}

\normalsize

\begin{center}
{\it Feuille de Travaux Dirigés 8}
\end{center}
\hrule


\ex
Traduire en code SPARC virtuel le programme suivant\,:

\begin{verbatim}
procedure quicksort(var tab: array[1..NMAX] of integer, int n);

procedure qs(g,d:integer);
var pos_pivot: integer;

function partition(g,d: integer): integer;
var i,j: integer;
    pivot: integer;
begin
    pivot := tab[g];
    i := g-1;
    j := d+1;
    while TRUE do
    begin
        repeat 
            j := j -1
        until tab[j] <= pivot;
        repeat
            i := i+1
        until tab[i] >= pivot;
        if i<j
            perm(tab[i],tab[j])
        else
            return j
    end
end;

begin
    if g<d then
    begin
        pos_pivot := partition(g,d);
        qs(g, pos_pivot);
        qs(pos_pivot+1, d)
    end
end;

begin
    qs(1,n);
end;
\end{verbatim}
\exe


\end{document}
