Zur MathePrisma-Startseite
Zur Modul-Startseite  


Sortierverfahren (Einleitung 1)
 

 
 





Die Aufgabe
 
Wir wollen eine Reihe von Datensätzen nach einem Kriterium, dem Schlüssel, sortieren.
Dies ist eine der wichtigsten Aufgaben beim kommerziellen Rechnereinsatz. Dazu einige  Beispiele.

Hier sind die Schlüssel immer natürliche Zahlen, die nach aufsteigender Größe sortiert werden sollen.

Zum Sortieren verwenden wir Algorithmen, die aus Schritten der folgenden Art bestehen:

  Jeder Schritt vergleicht zwei Schlüssel
und führt danach (eventuell) eine Vertauschung durch.

In folgendem Applet kannst du dich mit diesen beiden Schritten vertraut machen.

 
Schritte beim Sortieren
 
Wähle zwei Felder, klicke "Schlüsselvergleich" und dann "vertauschen" oder "nicht vertauschen". Es soll vertauscht werden, wenn die linke Zahl größer als die rechte ist.

 

 
Obwohl alle Sortierverfahren im Wesentlichen nur aus diesen beiden Schritten bestehen, sind ganz unterschiedliche Vorgehensweisen denkbar. Das folgende Applet illustriert zwei dieser Verfahren, die wir später auch behandeln werden. Welches ist schneller?
 
Wettrennen
 
 
Was kommt
 
Im Folgenden erwarten dich
  • ein anschaulicher, visueller Simulator,
  • Implementierungen in der Programmiersprache C,
  • Analysen der Idee, der Wirkungsweise und des Aufwandes
für vier wichtige Sortierverfahren.

 
Seite 1/17