Projekt:2020/Sortierverfahren

Seite zum Projekt "Processing" der Informatik EF im Schuljahr 2020/21.

Arbeitsauftrag

Wähle eine der folgenden Aufgaben aus:

1. Implementiere den Bubblesort-Algorithmus in der Scratch-Vorlage: https://scratch.mit.edu/projects/536837143
2. Implementiere den Selectionsort-Algorithmus in der Scratch-Vorlage: https://scratch.mit.edu/projects/536840094
3. Miss die Laufzeit der verschiedenen Sortierverfahren in Scratch: https://scratch.mit.edu/projects/536840268

Eine genauere Aufgabenbeschreibung findest du jeweils weiter unten.

Arbeitsauftrag

Implementiere den Bubblesort-Algorithmus in Scratch

Öffne die Scratch-Vorlage unter https://scratch.mit.edu/projects/536837143 und klicke oben rechts auf "Schau hinein". Sortiere nun die Blöcke in der Mitte so unterhalb von define bubbleSort, dass die Zahlen in der Liste mit dem Bubblesort sortiert werden.

Achtung:

• Du musst nur die vorhandenen Blöcke an die richtige Stelle schieben!
• Du benötigst nur die schon vorhandenen Blöcke und keine weiteren.
• Die Werte in den Blöcken sind schon passend eingestellt. Verändere sie nicht.
• Blöcke die schon zusammenhängen, sollen auch zusammen bleiben.
• Die Blöcke when green flag clicked und define tausche Element (a) mit Element (b) werden nicht benötigt und sollten nicht verschoben werden.

Arbeitsauftrag

Implementiere den Selectionsort-Algorithmus in Scratch

Öffne die Scratch-Vorlage unter https://scratch.mit.edu/projects/536840094 und klicke oben rechts auf "Schau hinein". Sortiere nun die Blöcke in der Mitte so unterhalb von define selectionSort, dass die Zahlen in der Liste mit dem Selectionsort sortiert werden.

Achtung:

• Du musst nur die vorhandenen Blöcke an die richtige Stelle schieben!
• Du benötigst nur die schon vorhandenen Blöcke und keine weiteren.
• Die Werte in den Blöcken sind schon passend eingestellt. Verändere sie nicht.
• Blöcke die schon zusammenhängen, sollen auch zusammen bleiben.
• Die Blöcke when green flag clicked und define tausche Element (a) mit Element (b) werden nicht benötigt und sollten nicht verschoben werden.

Arbeitsauftrag

Miss die Laufzeit der Sortieralgorithmen

Öffne das Scratch-Programm unter https://scratch.mit.edu/projects/536840268 und klicke auf den Button mit den vier Pfeilen oberhalb der Programmfensters, um das Fenster zu vergrößern. Klicke dann auf die grüne Flagge in der Mitte, damit das Programm startet.

Lege dir außerdem noch eine Tabelle in einem Tabellenkalkulation (z.B.: LibreOffice Calc) an. Notiere in der ersten Zeile der ersten beiden Spalten die Überschriften n und Zeit.

n	Zeit

Generiere nun verschiedene Listen mit Zufallszahlen in verschiedenen Konfigurationen (Aufsteigend, Absteigend, Zufällig) und lass sie von den drei vorhandenen Sortieralgorithmen sortieren. Notiere die Ergebnisse in der Tabelle (n steht für die Anzahl an Elementen).

Wenn du genug Messungen hast, erstellt pro Sortieralgorithmus ein Streudiagramm aus den Messdaten. Stelle eine Vermutung auf, welche Funktion das gezeigte Diagramm sein könnte.

Falls du Besonderheiten bemerkst (z.B. das ein Algorithmus für eine bestimmte Eingabe besonders schnell oder langsam ist), dann überlege dir eine Erklärung, warum dies so sein könnte.