• Quicksort
  • MaxKirchner
  • 03.06.2018
  • Allgemeine Hochschulreife
  • Informatik
  • 11
Um die Lizenzinformationen zu sehen, klicken Sie bitte den gewünschten Inhalt an.
  • https://www.tutory.de/w/1572e6d0

    Zu allen Aufgaben liegen am Pult Zettel mit Hilfestellungen, sofern du bei einer Aufgabe nicht weiter weißt.

    1
    Überlege, welche Anordnung der Zahlen 1,2,3,4,5,6,7 besonders viele Operationen benötigt, um mit dem Quicksort-Algorithmus sortiert zu werden.
    • Schreibe die Zahlenfolge auf.
    • Male das Rekursionsdiagramm auf.
    • Schreibe auf jeder Ebene, wie viele Listen-Operationen ausgeführt werden.
    • Führe alle oberen Aktionen erneut aus für eine Anordnung, die besonders wenige Operationen benötigt.
    2
    Erweitere das Programm aus der letzten Stunde so, dass du für den Quicksort- und Insertionsort-Algorithmus bei steigender Zufallszahlenanzahl die Anzahl der notwendigen Listenoperatoren angezeigt bekommst. Dein Ergebnis sollte dabei ähnlich aussehen wie die Tabelle unten.
    Gehe dabei wie folgt vor:
    • Erweitere die Listenklasse so, dass sie mitzählt, wie oft die Methoden next(), toFirst(), toLast(), getContent(), setContent(), insert(), append(), concat(), remove() aufgerufen werden. Diese Zahl soll durch eine neue Methode getOperation() abgefragt werden können.
    • Lasse dir Listen mit 1000, 2000, ..., 10.000 zufälligen Elementen erstellen und zu jeder Liste ausgeben, wieviele Listenoperationen Quicksort und Insertionsort zur Lösung benötigen.
      Achtung: Achte darauf, dass beide Algorithmen unsortiere Werte erhalten.
    Hilfestellungen

    Ihr erhaltet eine neue Sortieren.java, welche zusätzlich die Berechnung mittels Insertionsort enthält. Sofern ihr Aufgabenteil 1 nicht schafft, ist zusätzlich die erweiterte List.java verfügbar. Für Aufgabenteil 2 müsst ihr Listentest.java erweitern, wofür eine unfertige Vorlage mit Hilfestellungen vorliegt.

    Zahlen

    Operationen Quicksort

    Operationen Insertionsort

    1000

    4006

    506954

    2000

    8000

    1989557

    ...

    ...

    ...

    3
    Vergleiche die Ergebnisse mit der asymptotischen theoretischen Laufzeit.
    • Erstelle in Excel eine Tabelle mit 5 Spalten wie unten.
    • Trage die von dir berechneten Anzahl an Operationen ein.
    • Berechne mit Excel die theoretische Anzahl Operationen.
    • Plotte 2. und 3. Spalte sowie 3. und 4. jeweils in einem gemeinsamen XY-Diagramm (erste Spalte als X-Werte).
    • Interpretiere das Ergebnis.

    Zahlen

    Quicksort

    n2/2n^2/2

    Insertionsort

    nlognn\cdot\log n

    1000

    1000

    506954

    4006

    3000

    2000

    ...

    ...

    ...

    ...