HerunterladenAls PDF Herunterladen
  • Quicksort
  • MaxKirchner
  • 30.06.2020
  • Allgemeine Hochschulreife
  • Informatik
  • 11
Um die Lizenzinformationen zu sehen, klicken Sie bitte den gewünschten Inhalt an.
Name:
Quicksort
04.06.2018

Zu allen Auf­ga­ben lie­gen am Pult Zet­tel mit Hil­fe­stel­lun­gen, so­fern du bei einer Auf­ga­be nicht wei­ter weißt.

1
Über­le­ge, wel­che An­ord­nung der Zah­len 1,2,3,4,5,6,7 be­son­ders viele Ope­ra­tio­nen be­nö­tigt, um mit dem Quicksort-​Algorithmus sor­tiert zu wer­den.
  • Schrei­be die Zah­len­fol­ge auf.
  • Male das Re­kur­si­ons­dia­gramm auf.
  • Schrei­be auf jeder Ebene, wie viele Listen-​Operationen aus­ge­führt wer­den.
  • Führe alle obe­ren Ak­tio­nen er­neut aus für eine An­ord­nung, die be­son­ders we­ni­ge Ope­ra­tio­nen be­nö­tigt.
2
Er­wei­te­re das Pro­gramm aus der letz­ten Stun­de so, dass du für den Quicksort-​ und Insertionsort-​Algorithmus bei stei­gen­der Zu­falls­zah­len­an­zahl die An­zahl der not­wen­di­gen Lis­ten­ope­ra­to­ren an­ge­zeigt be­kommst. Dein Er­geb­nis soll­te dabei ähn­lich aus­se­hen wie die Ta­bel­le unten.
Gehe dabei wie folgt vor:
  • Er­wei­te­re die Lis­ten­klas­se so, dass sie mit­zählt, wie oft die Me­tho­den next(), to­First(), to­Last(), get­Con­tent(), set­Con­tent(), in­sert(), ap­pend(), con­cat(), re­mo­ve() auf­ge­ru­fen wer­den. Diese Zahl soll durch eine neue Me­tho­de ge­t­Ope­ra­ti­on() ab­ge­fragt wer­den kön­nen.
  • Lasse dir Lis­ten mit 1000, 2000, ..., 10.000 zu­fäl­li­gen Ele­men­ten er­stel­len und zu jeder Liste aus­ge­ben, wie­vie­le Lis­ten­ope­ra­tio­nen Quicks­ort und In­ser­ti­ons­ort zur Lö­sung be­nö­ti­gen.
    Ach­tung: Achte dar­auf, dass beide Al­go­rith­men un­sor­tie­re Werte er­hal­ten.
Hil­fe­stel­lun­gen

Ihr er­hal­tet eine neue Sor­tie­ren.java, wel­che zu­sätz­lich die Be­rech­nung mit­tels In­ser­ti­ons­ort ent­hält. So­fern ihr Auf­ga­ben­teil 1 nicht schafft, ist zu­sätz­lich die er­wei­ter­te List.java ver­füg­bar. Für Auf­ga­ben­teil 2 müsst ihr Lis­ten­test.java er­wei­tern, wofür eine un­fer­ti­ge Vor­la­ge mit Hil­fe­stel­lun­gen vor­liegt.

Zah­len

Ope­ra­tio­nen Quicks­ort

Ope­ra­tio­nen In­ser­ti­ons­ort

1000

4006

506954

2000

8000

1989557

...

...

...

3
Ver­glei­che die Er­geb­nis­se mit der asym­pto­ti­schen theo­re­ti­schen Lauf­zeit.
  • Er­stel­le in Excel eine Ta­bel­le mit 5 Spal­ten wie unten.
  • Trage die von dir be­rech­ne­ten An­zahl an Ope­ra­tio­nen ein.
  • Be­rech­ne mit Excel die theo­re­ti­sche An­zahl Ope­ra­tio­nen.
  • Plot­te 2. und 3. Spal­te sowie 3. und 4. je­weils in einem ge­mein­sa­men XY-​Diagramm (erste Spal­te als X-​Werte).
  • In­ter­pre­tie­re das Er­geb­nis.

Zah­len

Quicks­ort

In­ser­ti­ons­ort

1000

1000

506954

4006

3000

2000

...

...

...

...

Informatik
Angaben zu den Urhebern und Lizenzbedingungen der einzelnen Bestandteile dieses Dokuments finden Sie unter
https://www.tutory.de/entdecken/dokument/1572e6d0
x