• View
• Print

Informatik12-2

Bubblesort

Es gab am Montag für Minsort im wesentlichen 2 funktionierende Lösungen, die unterschiedlich schnell sind:

for( int m = 0; m < anzahl; m++){           
    for(int n = m+1; n < anzahl; n++) {
        if(größe(m) > größe(n)) {
            tausche(m, n);
        }
    }
}

und

for(int n = 1; n < anzahl; n++) {
    for(int x = 0; x < anzahl; x++){
        if(größe(x) > größe(n)) {
            tausche(x, n);
        }
    }
}

1. Vergleich der verschiedener Lösungen:
Führe beide Versionen aus und beschreibe so genau wie möglich, welche Schritte bei der langsameren Version unnötig sind.

2. Bubblesort
Auch die schnellere Version ist noch zu langsam. Untersuche als Alternative Bubblesort:
https://www.inf-schule.de/grenzen/komplexitaet/sortieren/sortieralgorithmen/bubblesort

Schaue das dort verlinkte YouTube-Video an und lies den Text. Im Internet gibt es viele weitere Seiten zu Bubblesort.
Implementiere Bubblesort in meiner BlueJ-Sortierumgebung und miss die Laufzeiten.

3. Vergleich der Laufzeiten
Wenn du am Montag ein schönes Diagramm gezeichnet hast, trage dort die Bubblesortlaufzeit zusätzlich ein. Wenn es nicht so schön geworden ist, erstelle ein neues Diagramm mit einem Vergleich der Laufzeiten von Minsort und Bubblesort.

4. Quadratische Laufzeit
Arne hat erkannt, dass die Laufzeit von Minsort quadratisch von der Anzahl der Steine abhängt. Das heißt, dass bei doppelt so vielen Steinen die Laufzeit viermal so groß ist. Alle anderen sind von einem exponentiellen Zusammenhang ausgegangen. Wohl weil das beim Rucksackproblem so war. Dort war es aber auch mit der schnellsten Version nicht mehr möglich, 60 Container zu verarbeiten. 60 Steine zu sortieren ist dagegen kein Problem. Eine quadratische Laufzeit ist als nicht ganz so schlimm wie eine exponentielle.

Um den quadratischen Zusammenhang zu verstehen, überlege wie viele Vergleiche if(größe(x) > größe(y)) das Programm bei 5, bei 10 und bei 20 Steinen durchführen muss.

Zusammenfassung
Schicke mir die Überlegungen zu den verschiedenen Minsortlösungen (1), das Bubblesortprogramm (2), das Diagramm mit beiden Laufzeiten (3) und deine Überlegungen zur Anzahl der Vergleiche (4) nach der Unterrichtsstunde am Freitag.