Theorie Icon

Lernziele
Du kannst...
  • Komplexere textuell beschriebene Algorithmen in Pythoncode überführen,
  • Laufzeiten von Algorithmen mit dem Time-Package messen,
  • eine zufällige Anzahl an Zufallsdaten erzeugen und in einer Liste speichern und
  • Laufzeiten von Algorithmen anhand einer Messung vergleichen.

Link: Materialien CodingDoJo week7

Übungsaufgaben

Löse folgende Übungsaufgaben. Die mit dem * gekennzeichnete Aufgaben sind zusätzliche Übungsaufgaben, die zur Wiederholung gedacht sind.

Selectionsort

Selectionsort basiert auf einer iterativen Suche nach dem Minimum. Dabei wird zu Beginn das kleinste Element bestimmt und an die erste Stelle getauscht. Danach wird in der restlichen Liste wieder das Minimum gesucht und an die zweite Stelle getauscht. Dieser Prozess bricht ab, sobald es nur noch ein Element in der restlichen Liste gibt.

Thonny Icon

A01 Vorbereitung
Generiere eine Liste mit 100 Einträgen mit Zufallszahlen zwischen 0 und 300.

Thonny Icon

A02 Implementierung des Algorithmus
Implementiere schrittweise den Sortieralgorithmus Selectionsort.
  1. Überlege also zuerst wie du das kleinste Element findest.
  2. Danach soll dieses mit dem ersten Element der Liste getauscht werden.
  3. Teste, ob dies funktioniert.
  4. Dieser Schritt soll nun solange wiederholt werden, bis das Ende der Liste erreicht ist.
  5. Dabei tauschst du im zweiten Durchgang nicht mit dem ersten Element, sondern mit dem zweiten Element der Liste. Setze dieses Vorgehen fort.
Mache deinen Code des Selectionsort wiederverwendbar, indem du ihn in eine Prozedur mit einem passenden Namen überführst.

Thonny Icon

A03 Testen
Generiere eine zweite Liste mit 1000 Einträgen und teste deine Prozedur mit beiden Listen.

Laufzeit testen

Thonny Icon

B01 Vorbereitung
  1. Nutze die time Funktion des time-Packages, um die Laufzeit deiner Sortierfunktion bei beiden Listen zu messen.
  2. Vergleiche die Laufzeit mit dem Bubblesortalgorithmus, indem du die Prozedur aus den Materialien in deinen Code kopierst. Lasse dir die Laufzeiten ausgeben.
  3. Erhöhe die Größe der Liste von 100 und 1000 auf 5000 und 10000.
  4. Vergleiche die Laufzeiten mit der Methode sort() des Listenobjekts.

5000 Zahlen
Bubblesort: 6.33607292175293
Selectionsort: 2.108869791030884
sort() 0.000995635986328125

10000 Zahlen
Bubblesort: 24.952056169509888
Selectionsort: 8.584328889846802
sort(): 0.010041236877441406

Insertionsort

Thonny Icon

C01 *Implementation Insertionsort
Wiederhole das Vorgehen aus den vorherigen Aufgaben mit dem Algorithmus Insertionsort. Dieser arbeitet wie folgt:
  1. Die ersten beiden Elemente von links werden verglichen und das kleinere nach links getauscht. Damit entsteht ein sortierter Bereich, welcher zwei Elemente umfasst.
  2. Jedes weitere Element wird an die entsprechende Stelle im bereits sortierten Bereich eingefügt. Hierzu wird das Element rechts vom sortierten Bereich mit allen Elementen im aktuell sortierten Bereich verglichen und falls nötig vertauscht.
  3. Falls keine Vertauschung erfolgt ist, dann ist das aktuelle Element korrekt einsortiert.

5000 Zahlen
Bubblesort: 6.344020843505859
Selectionsort: 2.0863451957702637
Insertionsort: 1.5312623977661133
sort(): 0.0009975433349609375

10000 Zahlen
Bubblesort: 24.239325761795044
Selectionsort: 8.470879554748535
Insertionsort: 5.908238649368286
sort(): 0.0019941329956054688