\documentclass[11pt]{article}
\usepackage[latin1]{inputenc}
\usepackage{german}
\usepackage{a4wide}

\parskip=0pt

\pagestyle{empty}

\begin{document}
\centerline{\it Vorlesung: Physik auf dem Computer I}
\bigskip
\centerline{\bf ÜBUNG 2} 
\medskip
\centerline{\it Kontrollstrukturen, Sortieren}

\bigskip
\bigskip

In dieser \"Ubung soll mittels eines einfachen Algorithmus ein Feld
von Zahlen sortiert werden, das vorher aus einer Datei eingelesen
wurde. Das Lesen aus einer Datei wird ganz \"ahnlich wie das Lesen von
einem Terminal gehandhabt, das Sie bereits in der letzten \"Ubung
kennengelernt haben. Dazu wird ein ``\verb|i|nput
\verb|f|ile\verb|stream|'' (auch \verb|cout| und \verb|cin| sind
``streams'') in der folgenden Weise angelegt:

\begin{verbatim}
#include <fstream>
using std::ifstream;   // import ifstream from namespace std:: to read
                       //   from file
#include <iostream>
using std::cout;       // ... and terminal i/o  

int main(){
  ifstream  input("filename");   // opens the file 'filename' in the
                       //   current directory 
  double    d;         // declare a floating point variable
  input  >> d;         // reads the first double from file, skips whitespace
  // ...
  cout   << d;         // print d to the terminal 
  return 0;
}  
\end{verbatim}

{\it Hinweis: Machen Sie nichts, was \"uber die Aufgabenstellung auf
  diesem Blatt wesentlich hinausgeht und benutzen Sie den einfachsten
  L\"osungsweg, der Ihnen einf\"allt. Machen Sie soweit wie Sie
  kommen: Der Schwierigkeitsgrad steigt gegen Ende des Blattes 
  --- alles f\"ur die L\"osung n\"otige sollten Sie im 
  bisherigen Vorlesungsskript (und Ihrem Kopf) finden.}

\bigskip 

\noindent {\bf Aufgabe 1.\ }
Die f\"ur diese Aufgabe ben\"otigte Datei \verb|data|  finden Sie in\\ 
\verb|/user0/sts/COMPUTERPHYSIK/BLATT2|.\\
Dort liegt auch das obige 
Programmger\"ust unter dem Namen \verb|fread.cc|.\\
(i) Kompilieren Sie das Programm \verb|fstream.cc| und verifizieren Sie, 
da\ss{} es die erste Zahl aus der Datei \verb|data| einlesen und wieder
ausgeben kann (beachten Sie, da\ss{} dazu der Dateiname mit dem im
Programm \"ubereinstimmen mu\ss{}). \\
(ii) F\"ugen Sie die Deklaration eines Feldes von Gleitkommazahlen in
das Programm ein und f\"ullen Sie dieses Feld innerhalb einer 
geeigneten Schleife mit den ersten 500 Werten aus der Datei \verb|data|.\\

\bigskip

\noindent {\bf Aufgabe 2.\ }
Die in dem eingelesenen Feld befindlichen Zahlen sollen mit einem
einfachen Algorithmus sortiert werden. Hierzu gehen wir in mehreren
Schritten vor.\\ 
(i) Wir wollen die gr\"o\ss{}te der eingelesenen Zahlen ermitteln. 
Eine Variable eines geeigneten Typs soll dazu verwendet werden, 
die bisher gr\"o\ss{}te gefundene Zahl aufzunehmen. Wie
kann man diese  Zahl sinnvoll initialiseren?\\
Schreiben Sie nun eine weitere Schleife, in der Sie durch
wiederholten Vergleich dieser Variable mit den Feldelementen 
den Maximalwert aller eingelesenen Werte ermitteln.  
\begin{verbatim}
  // loop prototype:
  for ( int i=0; i < 500; i++ ) {
    if ( ...  ) {
       do_something;
    }
  }    
\end{verbatim}

(ii) Modifizieren Sie diese Schleife nun so, da\ss{} das Maximum nicht
mehr durch Vergleich mit einer ``mitgeschleiften'' Variable ermittelt
wird, sondern dadurch, da\ss{} zwei aufeinanderfolgende Elemente des Feldes 
miteinander verglichen und ausgetauscht werden, falls sich dasjenige mit dem
kleineren Index als das gr\"o\ss{}ere erweisen sollte. \\[\medskipamount]
{\it Achten Sie
dabei auf die korrekte Wahl der Grenzen der Indexvariablen in der
Schleife. Der kleinste g\"ultige 
Index eines C/C++-Feldes ist null, der gr\"o\ss{}te die deklarierte
Feldgr\"o\ss{}e minus eins!}
Ein fast sicheres Indiz f\"ur ein Problem mit den Indizes sind 
{\it segmentation fault\/}s oder manchmal auch Schleifen, die nicht
abbrechen wollen.\\[\medskipamount]

Die gr\"o\ss{}te Zahl des Feldes ist durch das wiederholte Tauschen
wie eine ``Blase'' in Richtung gro\ss{}er Feldindizes gewandert. 
Ein weiterer Schritt fehlt noch, um einen vollst\"andigen
Sortieralgorithmus (``bubblesort'') zu erhalten.\\[\medskipamount]

(iii) Da die letzte Position des Feldes jetzt bereits 
die gr\"o\ss{}te Zahl enth\"alt, m\"ussen wir die im vorigen Schritt
angewandte Tauschvorschrift nur wiederum auf den unteren Teil des
Feldes anwenden. Dazu ben\"otigen wir eine zweite Schleife um die
erste herum, die den Index herunterz\"ahlt, bis zu dem die innere
laufen soll; etwa so:
\begin{verbatim}
  for ( int upper_index = ...; upper_index > ...; --upper_index ) {
     for ( int i= ...; i < ...; ++i ) {  
        // swap if necessary
     }
  }
\end{verbatim}
 
(iv) Lassen Sie sich die sortierten Zahlen auf dem Terminal
ausgeben.\\
 
\bigskip

\noindent {\bf Aufgabe 3.\ } {\it (freiwillig, anstelle 2.)}
Sollten Sie sich durch Aufgabe 2 nicht ausreichend gefordert f\"uhlen,
dann programmieren Sie eine Version von ``quicksort.'' (Hilfestellung
in Form von Kopien vom \"Ubungsleiter).


\vfill
\rightline{\tt Fragen an:  michi, sts@ica1.uni-stuttgart.de}
\end{document}

                                            











