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?
Hinweis: Diese Praxisaufgabe wurde so erstellt, dass sie auch gut im Unterricht mit älteren Schülerinnen und Schülern eingesetzt werden kann.
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.
Zum Spiel «Sortieralgorithmen mit Grafik» auf der Webseite von Scratch
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
Benutze für diese Aufgabe wieder das Programm von oben.
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.
Musterlösung
Der rote Balken ist der zurzeit 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 Quick Sort, 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.