Arbeitsblatt: Zeitvergleiche von drei Sortierverfahren (Grundlage für Arbeitsblätter)

Interrichtsidee Laufzeitanalyse bei Sortieralgorithmen Bubblesort – Minsort – optimierter Bubblesort Unterrichtsschritte 1. Ermitteln und Besprechen der Sortieralgorithmen 2. Systemzeit des Rechners vor und nach dem Sortieren abgreifen, in zwei Variablen speichern und daraus die Zeitspanne fürs Sortieren ermitteln 3. für Felder der Größe 1000 bis 10000 die Sortierzeit ermitteln und ausgeben (das ist natürlich die Durchschnittssortierzeit) 4. Zeitfunktionen erstellen (z.B. mit Excel) 5. Vermutung über das Wachstum aufstellen 6. Vermutung überprüfen (z.B. mit Excel) 1. 2. Die Sortieralgorithmen in der Übersicht Systemzeit (a) Bubblesort • • • Sortieren durch Vergleich der Nachbarelemente kein optimaler Bubblesort Felddurchlauf mit jeder Schleife auch im schon sortierten Feldbereich void sortieren (int Feldgroesse){ int Feldgroesse; feldErzeugen (n); double Zeit System.currentTimeMillis(); for (int 0; ; i) for (int 0; n-1; ) if (Feld [j] Feld [j1]) int Hilf Feld[j]; Feld[j] Feld [j1]; Feld [j1] Hilf; } Zeit System.currentTimeMillis() Zeit; System.out.println (Bubblesort: Feldgröße: Zeit Zeit); }// Bubblesort (b) Minsort • Sortieren durch Auswahl void minsort (int n){ // Variablen int MinPosition, EinfuegePosition; double StartZeit, EndZeit, Zeitspanne; int Hilf; feldErzeugen (n); StartZeit System.currentTimeMillis(); //Start Stoppuhr // Minsort for (int 0; ; i) EinfuegePosition i; MinPosition i; for (int i; n; j) if (a[j] a[MinPosition]) MinPosition j; Hilf a[MinPosition]; a[MinPosition] a[EinfuegePosition]; a[EinfuegePosition] Hilf; // for Schleife EndZeit System.currentTimeMillis(); // Stopp Stoppuhr Zeitspanne EndZeit StartZeit; // Berechnung der Zeitspanne System.out.println (Minsort: Feldgröße: Zeit Zeitspanne); }// void Minsort 1 Interrichtsidee Laufzeitanalyse bei Sortieralgorithmen Bubblesort – Minsort – optimierter Bubblesort (c) Optimierter Bubblesort • • Durchlauf des Feldes nur im noch nicht sortierten Teilfeld, Abbruch bei sortiertem Feld mittels boolscher Variablen void bubblesort (int n){ // Variablen boolean sortiert; double StartZeit, EndZeit, Zeitspanne; int Hilf; feldErzeugen (n); sortiert false; StartZeit System.currentTimeMillis(); //Start Stoppuhr for (int n-2; 0 i--) // Durchlauf von hinten nach vorne if (sortiert true) terminiert n i; break; else sortiert true; for (int 0; [j1]) Hilf a [j]; [j] a [j1]; [j1] Hilf; sortiert false; } // else // for Schleife EndZeit System.currentTimeMillis(); // Stopp Stoppuhr Zeitspanne EndZeit StartZeit; // Berechnung der Zeitspanne System.out.println (Optimierter Bubble: Feldgröße: Zeit Zeitspanne terminiert nach: terminiert Durchläufen.); }// void Bubblesort 3. • • • Ermitteln der Sortierzeit mittels Ausgabemethode (-Prozedur) Übergabe der Feldgröße Schleifendurchlauf in 1000er Schritten Zeitspanne wird in der sortierenden Methode ermittelt void Zeittest (int MaxFeldgroeße) for (int 1000;