Zur MathePrisma-Startseite
Zur Modul-Startseite  


Sortierverfahren (Einleitung 1 )
 

  
 
  
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.
Die Aufgabe
 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 können Sie sich mit diesen beiden Schritten vertraut machen.

 
 Wählen Sie zwei Felder, klicken Sie "Schlüsselvergleich" und dann "vertauschen" oder "nicht vertauschen". Es soll vertauscht werden, wenn die linke Zahl größer als die rechte ist.
Schritte beim Sortieren
 
  
 
 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 Sie

  • 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