\begin{slide}{Lineares Einfügen}

\begin{verbatim}
füge a[i] in a[0 .. i-1] ein = {
  Zahl k := i - 1;
  für (Zahl k von i-1 herab bis 0) {
     if ( a[k] <= a[k+1]) { 
        verlasse Schleife; 
     }
     tausche (a[k], a[k+1]);
  }
}
\end{verbatim}

Invariante:
\begin{itemize}
\item $a[0 \ldots n-1]$ ist Permutation von $A[0\ldots n-1]$
\item $a_0\le\ldots a_{k}$ und $a_{k+1}\le \ldots\le a_{i}$
\end{itemize}


\end{slide}

