einfuegesortieren.tex

\section{Anwendung: Einfügesortieren}

Als abschließendes und zusammenfassendes Beispiel für den ersten Teil dieses Skripts diskutieren wir nun noch ein etwas komplizierteres Beispiel.
Dabei wenden wir das bisher gelernte auf das schon erwähnte Sortierproblem an:
Ganze Zahlen $x_1, \ldots, x_n$ sollen eingelesen und dann sortiert ausgegeben werden.
Dafür unterteilen wir das Problem zunächst in kleinere Unterprobleme, das Einlesen der Zahlen und das Sortieren.
Dafür werden wir jeweils eine Funktion schreiben.

Wir beginnen mit dem Einlesen der zu sortierenden Zahlen.
Dafür nutzen wir wieder die Funktion \verb|scanf|.
Die Funktion, die wir \verb|read| nennen, sieht wie folgt aus
\begin{lstlisting}
#include <stdio.h>

int read(int array[], const int n)
{
  int i;
  for (i = 0; i < n; i++)
    {
      if (scanf("%d\n", &array[i]) == EOF)
        {
          break;
        }
    }
  if (i != n)
    printf("Sorry, es konnten nicht alle %d Zeichen eingelesen
                                %werden.\n", n);
  return i;
}
\end{lstlisting}
Die Funktion liest bis zu $n$ Zeichen ein, bzw. bis \verb|scanf| den Rückgabewert \verb|EOF| liefert.
Dieser Rückgabewert, der in \verb|stdio.h| definiert ist, bedeutet, dass \verb|scanf| das Ende des Eingabestroms erreicht hat.
Die eingelesenen Zahlen werde in \verb|array| gespeichert, das by reference übergeben wird.
Der Speicher für \verb|array| muss also von der aufrufenden Funktion bereitgestellt sein.
Der Rückgabewert unserer Funktion \verb|read| ist die Anzahl der eingelesenen Zahlen.

Als nächstes schreiben wir die Funktion zum Sortieren:
\begin{lstlisting}
void sort(int sortiert[], int unsortiert[], const int n)
{
  for (int i = 0; i < n; ++i)
    {
      sortiert[i] = unsortiert[i];
      for (int j = i; j > 0; --j)
        {
          if (sortiert[j] < sortiert[j - 1])
            {
              int swap = sortiert[j];
              sortiert[j] = sortiert[j - 1];
              sortiert[j - 1] = swap;
            }
          else
            break;
        }
    }
}
\end{lstlisting}
Diese Funktion hat drei Eingabeparameter: Das Array, dass die sortierten Zahlen enthalten soll, das Array, dass die zu sortierenden Zahlen enthält, und die Anzahl an zu sortierenden Zahlen.
Wieder muss die aufrufende Funktion dafür Sorge tragen, dass für beide Arrays ausreichend Speicher bereitgestellt wurde.
Überzeugen Sie sich bei den übrigen Zeilen, dass diese wirklich die $n$ Zahlen durch Einfügen in das Array \verb|sortiert| sortiert.
Als neues Element haben wir an dieser Stelle den Rückgabewert von \verb|sort| als \verb|void| deklariert.
Das bedeutet, dass die Funktion keinen Rückgabewert hat.

Bleibt noch die \verb|main| Funktion, die wie folgt aussieht:
\begin{lstlisting}
#include <stdio.h>

int read(int array[], const int n);
void sort(int sortiert[], int unsortiert[], const int n);

int main()
{
  const int MAXNUM = 10000;
  int array[MAXNUM], sortiert[MAXNUM];

  // read the numbers
  int actual_length = read(array, MAXNUM);

  // sort the numbers
  sort(sortiert, array, actual_length);

  // print them on the screen
  for (int i = 0; i < actual_length; ++i)
    {
      printf("%d ", array[i]);
    }
  printf("\n");
}
\end{lstlisting}
Hier haben wir schon von der Möglichkeit Gebrauch gemacht, dass man Funktionen deklarieren kann, und die Definition später stattfinden kann.
Man kann also beispielsweise in eine Datei \verb|sort.c| erst den Code für die \verb|main| Funktion kopieren, und im Anschluss daran den Code für die beiden Funktionen.
Übersetzen kann man dann mit
\begin{verbatim}
gcc --std=c99 -o sort sort.c
\end{verbatim}
Der Name der ausführbaren Datei ist dann \verb|sort|.
Diese kann im Prinzip mit
\begin{verbatim}
$> ./sort
\end{verbatim}
von der Konsole ausgeführt werden.
Allerdings brauchen wir erst noch Eingabedaten.
Damit nicht alles von Hand eingegeben werden muss, nutzen wir die Funktionalität von Linux und leiten den Eingabestrom aus einer Datei um.
Wir erzeugen erst eine Textdatei mit Namen \verb|data.dat| mit folgenden Zeilen
\begin{verbatim}
12
77
25
43
4
\end{verbatim}
Damit kann man das Programm von der Kommandozeile wie folgt ausführen:
\begin{verbatim}
$> ./sort < data.dat
4 12 25 43 77
\end{verbatim}
Im zweiten Teil werden wir zeigen, wie man direkt mit C aus einer Datei einlesen kann.

\endinput