Musterlösung zum 16.02.2021

Zu den Aufgaben vom 16.02.2021 ist ein komplettes Verzeichnis Sortieren in der ZIP-Datei Sortieren.zip zum Download verfügbar. Es ist ein fertiges BlueJ-Projekt.

1. Rechte Maustaste auf Sortieren.zip und "Ziel speichern unter" wählen.
2. In einem beliebigen Verzeichnis auf dem PC (Annahme: C:\InfoQ1) abspeichern unter dem gleichen Namen.
3. Mit dem Datei-Explorer (oder Finder auf Mac) zum Verzeichnis C:\InfoQ1 wechseln.
4. Dort liegt die Datei Sortieren.zip. Mit der rechten Maustaste auf dem Dateinamen erscheint das Kontextmenü. Wähle "Alle extrahieren".
   Es erscheint: Dateien werden in diesen Ordner extrahiert: C:\InfoQ1\Sortieren
   Wähle "Extrahieren".
5. Im Verzeichnis C:\InfoQ1 entsteht das Unterverzeichnis Sortieren.
6. Wechsle in dieses Verzeichnis mit dem Datei-Explorer.
7. Im Verzeichnis ist die Datei package.bluej. Durch Anklicken dieser Datei müsste BlueJ starten.
8. Jetzt kannst du die Java-Datei SortierenMinBubbleBeispiel.java bearbeiten.
9. Für die weitere Arbeit legst du einfach in diesem Verzeichnis mit dem Datei-Explorer eine Kopie dieser Datei an und benennst sie z. B. in MeinMinBubbleBeispiel.java um. Wenn du dann wieder auf package.bluej klickst, siehst du die neue Datei auch im BlueJ-Fenster.

Auftrag 1:

Informiere dich in dem Wikipedia-Artikel über die Gaußsche Summenformel. Lies auch die Geschichte über den neunjährigen kleinen Gauß. Nach dieser Formel ergeben sich die folgenden Summen:

1 + 2 + 3 + 4 + 5 =

1 + 2 + ... + 99 + 100 =

1 + 2 + ... + 199 + 200 =

1 + 2 + ... + 999 + 1000 =

Hinweis: Diese Summenformel habe ich gestern in der Klasse 5B behandelt.

Auftrag 2:

Wir betrachten noch einmal den Minsort-Algorithmus:

  public void minsort()
  { int minpos;
    for (int i=0; i <= maxIndex; i++)
    {    minpos = i;
         for (int k=i+1; k <= maxIndex; k++)
              if (feld[k] < feld[minpos])
                   minpos = k;
         if (minpos > i) vertausche(i, minpos);
    } // for i
  }  // minsort

Bei einem Feld mit n Elementen gibt es n-1 Durchgänge durch das Feld. Mache dir diesen Zusammenhang bei einem kleinen Feld mit z.B. n=4 Elementen klar (maxIndex = 3):

Beim ersten Durchgang vergleicht man die Positionen 1 bis 3 mit Position 0.
Beim zweiten Durchgang vergleicht man die Positionen 2 bis 3 mit Position 1.
Beim dritten Durchgang vergleicht man die Positionen 3 (bis 3) mit Position 2.

Jetzt betrachten wir wieder das Feld mit n Elementen. Ergänze.

Die Gesamtzahl der Vergleiche ist dann A(n) = 1 + 2 + .

Mit der Gaußschen Summenformel ist dann A(n) = .

Dann ergibt sich

A(10.000) = .

A(20.000) = .

A(40.000) = .

Wenn man annimmt, dass die Anzahl der Vergleiche beim Sortieren eines zufällig gefüllten Feldes etwa proportional zum Zeitbedarf ist, dann ergibt sich etwa folgender Zusammenhang (Ergänze Verdopplung, Verdreifachung, o.a.!):