Praxisaufgabe 2: Sortieralgorithmen vergleichen (Fortgeschrittene) – digibasics
Zum Hauptinhalt springen

Praxisaufgabe 2: Sortieralgorithmen vergleichen (Fortgeschrittene)

Es gibt ganz verschiedene Sortieralgorithmen. Jetzt musst du den Schnellsten Sortieralgorithmus finden. Schau dir das Scratch-Programm an und experimentiere damit. Welcher Sortieralgorithmus ist der Schnellste? Ist es der Schnellste, egal wie lang deine Liste ist? 

Probiere die Sortieralgorithmen mit einer sehr kleinen Liste (unter 100 Elemente aus). Gibt es jetzt noch Unterschiede zwischen den Sortieralgorithmen?

Anleitung

Drücke auf die grüne Flagge um das Programm zu starten. Drücke dann auf einen der Sortieralgorithmen auf der rechten Seite. Sobald der Knopf rot wird, ist der Sortieralgorithmus fertig. 

Wenn du einen anderen Sortieralgorithmus benutzen möchtest, musst du zuerst eine neue Liste erstellen. Drücke dazu auf «Neue Liste». 

Unten links kannst du die Länge der Liste ändern. Aber denk daran, du musst zuerst «Neue Liste» drücken, damit du eine Liste mit der benötigten Länge hast.

https://scratch.mit.edu/projects/649449989/

Musterlösung

Im Normalfall ist der Quick Sort der Schnellste der drei Sortieralgorithmen. Hat es nur wenige Daten, sind die drei Sortieralgorithmen ähnlich schnell. 

Zusatz

Wenn du willst kannst du den Sortieralgorithmen auch bei der Arbeit zuschauen. Findest du heraus, wie sie funktionieren? Tipp: Was ist die Rolle des roten Balkens? Was ist die Rolle des gelben Balkens? 

Achtung: Wenn das Programm auch eine Grafik erzeugen muss, kannst du die Geschwindigkeit der Algorithmen nicht mehr vergleichen.

https://scratch.mit.edu/projects/660741433/

Musterlösung Zusatz

Der rote Balken ist der zur Zeit ausgewählte Wert. Er wird mit dem gelben Wert verglichen. 

Der Unterschied zwischen den verschiedenen Sortieralgorithmen ist die Auswahl der beiden Werte. 

Beim Bubble Sort wird der ausgewählte Wert jeweils mit dem nächsten Wert verglichen. Ist der nächste Wert kleiner, wird die Position gewechselt. Ist er grösser, wird der grössere Wert zum ausgewählten Wert. 

Beim Insertion Sort wird der ausgewählte Wert der Reihe nach mit allen bisher sortierten Werten verglichen. Sobald die passende Position gefunden wurde, bleibt der Wert dort. 

Beim Quick Sort wird jeweils zuerst ein Vergleichswert (Pivot) ausgesucht. Am besten funktioniert der Quicksort, wenn der Pivot in der Mitte des Wertebereichs liegt. Danach werden die Werte auf beiden Seiten mit dem Pivot verglichen. Alle Werte, die grösser sind, als der Pivot werden auf eine Seite verschoben. Alle kleineren Werte werden auf die andere Seite geschoben. Danach wird wiederum ein Pivot auf jeder der beiden Seiten bestimmt und das Verfahren erneut angewendet.