quicksort.tex

A Library of Efficient Data Types and Algorithms,封装了常用的ADT及其相关算法的软件包

\documentclass[12pt,a4paper]{article}
\usepackage[latin1]{inputenc}
\usepackage[german]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{amsthm}

\setlength{\oddsidemargin}{-0.5cm}
\setlength{\evensidemargin}{-1cm}
\setlength{\textwidth}{17cm}
\setlength{\textheight}{25cm}
\setlength{\headsep}{1cm}
\setlength{\topmargin}{-1.5cm}
\setlength{\parindent}{0cm}

\begin{document}

\theoremstyle{plain}  \newtheorem{satz*}{Satz}[]

\section*{Quicksort}

Quicksort ist ein allgemeines Sortierverfahren vom Typ "<Teile und Herrsche">. 
Es beruht auf dem Zerlegen eines zu sortierenden Feldes in zwei Teile und dem anschlie遝nden 
Sortieren der beiden Teile unabh鋘gig voneinander. Der Algorithmus hat folgende Gestalt:

\begin{verbatim}
void quicksort (int A[], int l, int r)
{
  if(l >= r) return;  
  int i = l;
  int j = r+1;
  int v = A[l];
  for (;;)
  {
    while(A[++i] < v && i < r);
    while(A[--j] > v);
    if(i >= j) {
      swap(A, l, j);    			
      break;
    }
    swap(A, i, j);
  }
  quicksort(A, l, j-1);
  quicksort(A, j+1, r);
}
\end{verbatim}
\mbox{}\\[-1ex]
Die Parameter {\tt l} und {\tt r} begrenzen das Teilfeld innerhalb des urspr黱glichen Feldes, 
welches zu sortieren ist; der Aufruf {\tt quicksort(A, 0, A.size()-1)} sortiert das gesamte Feld. 
\\\\[-1ex]
Das entscheidene Element der Methode ist der Programmcode innerhalb der unendlich Schleife 
{\tt for(;;)}, der das Feld so umordnet, da