• View
• Print

Informatik12-1

Minsort

Obwohl wir mit der Untersuchung der Laufzeiten des Rucksackproblem und ähnlicher Probleme noch nicht ganz fertig sind, brechen wir das jetzt ab und untersuchen jetzt erst mal Sortierprogramme. Auch bei ihnen spielt die Laufzeit eine entscheidende Rolle. Öffnet das Projekt Sortieren.zip? oder kopiert folgenden Quelltext in eine neu BlueJ-Klasse:

public class Sortieren extends sortieren.Sortierprogramm
{
    @Override public void sortieren(int anzahl)
    {
        for(int n = 1; n < anzahl; n++) {
            if(größe(0) > größe(n)) {
                tausche(0, n);
            }
        }        
    }
    // **************************************************************************************************
    public static void main() { xPanel.XPanel.startInFrame(new Sortieren(), 500, 400, "Sortieren"); }
}

Eventuell müsst ihr noch xPanel.jar? in .../BlueJ/lib/userlib kopieren (sollte da aber eigentlich schon drin stehen). Wenn ihr das Programm startet und Enter drückt, wird der erste Stein der Reihe nach mit allen weiteren Steinen verglichen. Falls der erste Stein größer ist als ein weiter hinten stehender Stein, werden beide getauscht.

Aufgabe für Montag 16.3.

Ergänzt das Programm so, dass anschließend der 2. Stein mit allen weiter hinten stehenden Steinen verglichen und gegebenenfalls getauscht wird.
Dann der 3. usw., bis alle Steine sortiert sind.
Ändert die Anzahl der Steine und untersucht die Laufzeit. Zeichnet ein Diagramm mit der Anzahl der Steine auf der x- und der Zeit auf der y-Achse. Welcher Zusammenhang besteht?
Schickt mir euer Programm, ein Bild des Diagramms und eure Überlegungen zur Laufzeit per Mail.