\chapter{Quicksort} 
\label{chapter:Quicksort}

\renewcommand{\labelitemi}{$\bullet$}
\renewcommand{\labelitemii}{$\bullet$}

\renewcommand{\theenumi}{(\arabic{enumi})}
\renewcommand{\labelenumi}{\theenumi}

Sortieren eines Reihenstücks (mindestens 2 Elemente\footnote{\label{foot:1}Das Verfahren verhält sich auch noch bei einem Element gutartig,ist aber sinnlos.}):

\begin{itemize}

  \item Zunächst legt man einen Trenner fest.Dies ist ein beliebig gewählter Wert aus dem zu sortierenden Reihenstück.
  
  \item Danach vertauscht man Elemente in dem Reihenstück derart,dass zu Begin der Reihe ein Teilbereich entsteht mit Elementen kleiner/gleich dem Trenner und zum Ende der Reihe ein Teilbereich mit größer/gleich dem Trenner.Der dazwischen liegende Bereich besteht maximal aus einem Element;dieses ist dann gleich dem Trenner.\newline\newline
Wie tauscht man die Elemente und erstellt die Teilbereiche?
  
  \begin{itemize}
  
    \item  Man durchsucht die Reihe ''von links''  und ''von rechts'' und tauscht ungeeignete Elemente paarweise gegeneinander aus,bis die gewünschte Zerlegung erreicht ist.
    
    \item Aus Effektivitätsgründen tauscht man auch immer Elemente vom Wert des Trenners,siehe Anmerkungen \ref{l1} und nimmt auch einige ansonsten nicht erforderliche Tauschvorgänge hin,siehe \ref{l2} und \ref{l3}.
    
  \end{itemize}
  
  \item Dann wendet man das Sortierverfahren auf die entstandenen Teilbereiche an (Rekursion),sofern diese mindestens noch zwei Elemente enthalten.
  
\end{itemize}
Zur einfacheren Programmierung von Quicksort \index{Quicksort} ein Struktogramm,siehe Abbildung \ref{fig:strukto}\index{Abbildung \ref{fig:strukto}}.

\begin{figure}
\begin{struktogramm}(140,245)[Sortieren einer Reihe Hauptarray aufsteigend/absteigend,und gleichzeitiger Sortierung der Reihe Nebenarray gemäß Hauptarray,zwischen Index linkerIndex und Index rechterIndex]
\assign{\pComment{Setze Hauptarray = HauptarrayNebenarray[0] und Nebenarray = HauptarrayNebenarray[1]}}
\assign{\pComment{Bestimme den Trenner Trenner}}
\assign{\pComment{Setze linkerLaufindex = linkerIndex und rechterLaufindex = rechterIndex}}
\while{true}
\while{Solange wie Hauptarray[linkerLaufindex] < Trenner / Hauptarray[linkerLaufindex] > Trenner // Suche nach Tauschkandidaten \ref{l1}}
\assign{\pComment{Erhöhe linkerLaufindex um 1 // Suche nach Tauschkandidaten \ref{l1}}}
\whileend
\while{Solange wie Trenner < Hauptarray[rechterLaufindex]  / Trenner > Hauptarray[rechterLaufindex] // Suche nach Tauschkandidaten \ref{l1} }
\assign{\pComment{Vermindere rechterLaufindex um 1 // Suche nach Tauschkandidaten \ref{l1}}}
\whileend
\ifthenelse{3}{3}{\pExp{linkerLaufindex > rechterLaufindex}}{ja}{nein}
\assign{\pComment{break}}
\change%
\ifend%
\assign{\pComment{Tausche Hauptarray[linkerLaufindex] mit Hauptarray[rechterLaufindex] // Tauschen \ref{l2} \ref{l3}}}
\assign{\pComment{Tausche Nebenarray[linkerLaufindex] mit Nebenarray[rechterLaufindex] // Tauschen \ref{l2} \ref{l3}}}
\assign{\pComment{Erhöhe linkerLaufindex um 1 // Weitergehen}}
\assign{\pComment{Vermindere rechterLaufindex um 1 // Weitergehen}}
\ifthenelse{3}{3}{\pExp{linkerLaufindex > rechterLaufindex}}{ja}{nein}
\assign{\pComment{break}}
\change%
\ifend%
\whileend
\ifthenelse{3}{3}{\pExp{linkerIndex < rechterLaufindex}}{ja}{nein}
\assign{\pComment{Sortiere HauptarrayNebenarray zwischen linkerIndex und rechterLaufindex}}
\change%
\ifend%
\ifthenelse{3}{3}{\pExp{linkerLaufindex < rechterIndex}}{ja}{nein}
\assign{\pComment{Sortiere  HauptarrayNebenarray zwischen linkerLaufindex und rechterIndex}}
\change%
\ifend%
\end{struktogramm}
\caption{Struktogramm von Quicksort}
\label{fig:strukto}
\end{figure}\newpage

Anmerkungen:

\begin{enumerate}

  \item \label{l1} Warum Vergleich '<'/ '>' und nicht '<='/ '>='?\newline
Bei '<='/ '>=' müßte es jeweils noch ein Element geben,welches größer bzw.kleiner / kleiner bzw.größer (zweite Wiederholung) als der Trenner ist,damit die Suche abbricht.Deratiges ist aber nicht gesichert!
  
  \item \label{l2} Es kann passieren,daß Hauptarray[linkerLaufindex] == Trenner und Hauptarray[rechterLaufindex] == Trenner ist.Dann wird unnötig getauscht.Dies kann durch eine Abfrage verhindert werden,deren laufende Ausführung aber auch nicht effektiver ist.
  
  \item \label{l3} Für linkerLaufindex == rechterLaufindex ist das Vertauschen sinnlos,aber harmlos;es darf aber nicht schon abgebrochen werden,da der Punkt ''Weitergehen'' noch unbedingt zu erfolgen hat.

\end{enumerate}